首页 > 代码库 > 【hihoCoder】第20周 线段树
【hihoCoder】第20周 线段树
题目：
输入
每个测试点（输入文件）有且仅有一组测试数据。
每组测试数据的第1行为一个整数N，意义如前文所述。
每组测试数据的第2行为N个整数，分别描述每种商品的重量，其中第i个整数表示标号为i的商品的重量Pi。
每组测试数据的第3行为一个整数Q，表示小Hi进行的操作数。
每组测试数据的第N+4~N+Q+3行，每行分别描述一次操作，每行的开头均为一个属于0或1的数字，分别表示该行描述一个询问和一次商品的价格的更改两种情况。对于第N+i+3行，如果该行描述一个询问，则接下来为两个整数Li, Ri，表示小Hi询问的一个区间[Li, Ri]；如果该行描述一次商品的价格的更改，则接下来为三个整数Li，Ri，NewP，表示标号在区间[Li, Ri]的商品的价格全部修改为NewP。
对于100%的数据，满足N<=10^5，Q<=10^5, 1<=Li<=Ri<=N，1<=Pi<=N, 0<Pi, NewP<=10^4。
输出
对于每组测试数据，对于每个小Hi的询问，按照在输入中出现的顺序，各输出一行，表示查询的结果：标号在区间[Li, Ri]中的所有商品的价格之和。
说白了，就是更新一个区间的值，和询问一个区间的值的和
解法：
题目上说了线段树，那就肯定是线段树了。
我也是最近才学的，其实就是叶子结点是一个数字的值，向上的父节点就是它所包含的数字范围的和的值。
线段树快也主要是在查询时不用一个一个数字的加，而是遇到符合的区间后可以直接获取整个区间的和。
线段树的结点包括：左右范围、区间和的值、左右子树
typedef struct Node{ int left, right; //区间左右值 int totalCharge; //区间总价格 Node *pLeft, *pRight; //子区间指针}Node;
线段树的操作主要是查询和更新
用指针的线段树代码如下，测试结果超时。
#include <stdio.h>#include <stdlib.h>int Num[100001] = {0};int sum;typedef struct Node{ int left, right; //区间左右值 int totalCharge; //区间总价格 Node *pLeft, *pRight; //子区间指针}Node;Node * build(int l, int r) //建立线段树{ Node * root = (Node*)malloc(sizeof(Node)); root->left = l; root->right = r; if(l == r) { root->totalCharge = Num[l]; root->pLeft = NULL; root->pRight = NULL; } else { int mid = (r + l) >> 1; root->pLeft = build(l, mid); root->pRight = build(mid + 1, r); root->totalCharge = root->pLeft->totalCharge + root->pRight->totalCharge; } return root;}void updateTree(Node * root, int l, int r, int newP){ if(root->left == root->right) { root->totalCharge = newP; return; } int m = (root->left + root->right) >> 1; if(l > m) //都在右子树 { updateTree(root->pRight, l, r, newP); root->totalCharge = root->pLeft->totalCharge + root->pRight->totalCharge; } else if(r <= m) //都在左子树 { updateTree(root->pLeft, l, r, newP); root->totalCharge = root->pLeft->totalCharge + root->pRight->totalCharge; } else { updateTree(root->pLeft, l, m, newP); updateTree(root->pRight, m + 1, r, newP); root->totalCharge = root->pLeft->totalCharge + root->pRight->totalCharge; }}void getRangeNum(Node * root, int data1, int data2){ if(data1 == root->left && data2 == root->right) //区间恰好重合 { sum += root->totalCharge; return; } int m = (root->left + root->right) >> 1; if(data1 > m) //都在右子树 { getRangeNum(root->pRight, data1, data2); } else if(data2 <= m) //都在左子树 { getRangeNum(root->pLeft, data1, data2); } else { getRangeNum(root->pLeft, data1, m); getRangeNum(root->pRight, m + 1, data2); }}int main(){ Node * root = NULL; int count = 0; int N; //一共有多少组数据 int OperateNum = 0; int cmd; scanf("%d", &N); while(N--) { scanf("%d", Num + count++); } root = build(0, count); scanf("%d", &OperateNum); while(OperateNum--) { scanf("%d",&cmd); if(cmd == 0) //询问 { int l, r; scanf("%d %d", &l, &r); sum = 0; getRangeNum(root, l - 1, r - 1); printf("%d\n",sum); } else if(cmd == 1)//更改 { int l, r, newP; scanf("%d %d %d", &l, &r, &newP); updateTree(root, l - 1, r - 1, newP); } } return 0;}
指针的超时了，想当然的建立了数组的线段树
typedef struct Node{ int value; int left, right;}Node;Node SegmentTree[4 * maxind] = {0};
我建立线段树是按根节点是0这样建立的，所以 node 的左子树为 2 * node + 1, 右子树为 2 * node + 2。而且查询时，如果问2-5，则应输入1-4，因为我这样是从0开始的，而题目中是从1开始的。
但网上很多是从1开始的，那样左子树就是2 * node, 右子树为 2 * node + 1，这里注意。
结果，居然又超时了！！
#include <stdio.h>#include <stdlib.h>const int maxind = 100000;typedef struct Node{ int value; int left, right;}Node;int Num[maxind] = {0};Node SegmentTree[4 * maxind] = {0};int sum;void build(int node, int l, int r) //建立线段树{ SegmentTree[node].left = l; SegmentTree[node].right = r; if(l == r) { SegmentTree[node].value = Num[l]; } else { int m = (l + r) >> 1; build(2 * node + 1, l, m); build(2 * node + 2, m + 1, r); SegmentTree[node].value = SegmentTree[2 * node + 1].value + SegmentTree[2 * node + 2].value; }}void updateTree(int node, int l, int r, int newP){ if(l == SegmentTree[node].left && r == SegmentTree[node].right && l == r) { SegmentTree[node].value = newP; return; } int m = (SegmentTree[node].left + SegmentTree[node].right) >> 1; if(l > m) //都在右子树 { updateTree(2 * node + 2, l, r, newP); SegmentTree[node].value = SegmentTree[2 * node + 1].value + SegmentTree[2 * node + 2].value; } else if(r <= m) //都在左子树 { updateTree(2 * node + 1, l, r, newP); SegmentTree[node].value = SegmentTree[2 * node + 1].value + SegmentTree[2 * node + 2].value; } else { updateTree(2 * node + 1, l, m, newP); updateTree(2 * node + 2, m + 1, r, newP); SegmentTree[node].value = SegmentTree[2 * node + 1].value + SegmentTree[2 * node + 2].value; }}void getRangeNum(int node, int data1, int data2){ if(data1 == SegmentTree[node].left && data2 == SegmentTree[node].right) //区间恰好重合 { sum += SegmentTree[node].value; return; } int m = (SegmentTree[node].left + SegmentTree[node].right) >> 1; if(data1 > m) //都在右子树 { getRangeNum(2 * node + 2, data1, data2); } else if(data2 <= m) //都在左子树 { getRangeNum(2 * node + 1, data1, data2); } else { getRangeNum(2 * node + 1, data1, m); getRangeNum(2 * node + 2, m + 1, data2); }}int main(){ int count = 0; int N; //一共有多少组数据 int OperateNum = 0; int cmd; scanf("%d", &N); while(N--) { scanf("%d", Num + count++); } build(0, 0, count - 1); scanf("%d", &OperateNum); while(OperateNum--) { scanf("%d",&cmd); if(cmd == 0) //询问 { int l, r; scanf("%d %d", &l, &r); sum = 0; getRangeNum(0, l - 1, r - 1); printf("%d\n",sum); } else if(cmd == 1)//更改 { int l, r, newP; scanf("%d %d %d", &l, &r, &newP); updateTree(0, l - 1, r - 1, newP); } } return 0;}
只好再去学习lazy思想，每次并不都更新到叶子结点，而是在吻合的一整段区间上做标记，等查询到更细的区间时再把子区间更新。
typedef struct Node{ long long value; long long lnc; bool tag; int left, right;}Node;Node SegmentTree[4 * maxind] = {0};
其中
tag 标记这个区间的数字是否是更新的，true为是，即整个区间的和是正确的，但它的子区间都没有更新
lnc 记录需要更新的区间，应该被更新的值是什么
下面给出更新和查询的伪代码，特别注意，区间获取值时间的一致性问题，所有的区间都是在获得tag标记的同时获得该区间正确的值的，如果这里不一致后面会出错。
还有，就是更新时也要做tag标签的向下调整，我就是在这里卡了好久。
更新的伪代码：
输入：根节点node, 更新区间 l,r 新值 newPvoid update{ if(l,r区间与根节点区间完全吻合) { 更新根节点的标记，更新值，区间和 return; } if(不满足上面条件，但是根节点tag=true) //即还有没向下更新的成分 { 向下传递更新的信息 包括左右子树的标记，更新值，区间和 //注意，都是在区间获得tag标记的同时得到区间的范围值 } 根据数字范围，选择更新左右子树的部分 获的该区间的和}
查询的伪代码：
输入：根节点，查询区间 l, rgetRangeNum{ if(查询区间范围与根节点范围完全一致) { sum+=根节点值 return; } if(不满足上面条件，但是根节点tag=true) //即还有没向下更新的成分 { 向下传递更新的信息 包括左右子树的标记，更新值，区间和 //注意，都是在区间获得tag标记的同时得到区间的范围值 } 根据数字范围，选择查询左右子树的部分，递归查询}
最后AC的代码如下： 话说AC的时候我感动的都要哭了.....
#include <stdio.h>#include <stdlib.h>const int maxind = 100000;typedef struct Node{ long long value; long long lnc; bool tag; int left, right;}Node;long long Num[maxind] = {0};Node SegmentTree[4 * maxind] = {0};long long sum;void build(int node, int l, int r) //建立线段树{ SegmentTree[node].left = l; SegmentTree[node].right = r; SegmentTree[node].lnc = 0; SegmentTree[node].tag = false; if(l == r) { SegmentTree[node].value = Num[l]; } else { int m = (l + r) >> 1; build(2 * node + 1, l, m); build(2 * node + 2, m + 1, r); SegmentTree[node].value = SegmentTree[2 * node + 1].value + SegmentTree[2 * node + 2].value; }}void updateTree(int node, int l, int r, int newP){ if(l == SegmentTree[node].left && r == SegmentTree[node].right) { SegmentTree[node].lnc = newP; SegmentTree[node].value = newP * (r - l + 1); SegmentTree[node].tag = true; return; } if(SegmentTree[node].tag == true) //注意 更新的时候也要把tag下移 { SegmentTree[2 * node + 1].lnc = SegmentTree[node].lnc; SegmentTree[2 * node + 2].lnc = SegmentTree[node].lnc; SegmentTree[2 * node + 1].tag = true; SegmentTree[2 * node + 2].tag = true; SegmentTree[2 * node + 1].value = http://www.mamicode.com/(SegmentTree[2 * node + 1].right - SegmentTree[2 * node + 1].left + 1) * SegmentTree[2 * node + 1].lnc; SegmentTree[2 * node + 2].value = http://www.mamicode.com/(SegmentTree[2 * node + 2].right - SegmentTree[2 * node + 2].left + 1) * SegmentTree[2 * node + 2].lnc; SegmentTree[node].lnc = 0; SegmentTree[node].tag = false; } int m = (SegmentTree[node].left + SegmentTree[node].right) >> 1; if(l > m) //都在右子树 { updateTree(2 * node + 2, l, r, newP); } else if(r <= m) //都在左子树 { updateTree(2 * node + 1, l, r, newP); } else { updateTree(2 * node + 1, l, m, newP); updateTree(2 * node + 2, m + 1, r, newP); } SegmentTree[node].value = SegmentTree[2 * node + 1].value + SegmentTree[2 * node + 2].value;}void getRangeNum(int node, int data1, int data2){ if(data1 == SegmentTree[node].left && data2 == SegmentTree[node].right) //区间恰好重合 { sum += SegmentTree[node].value; return; } int m = (SegmentTree[node].left + SegmentTree[node].right) >> 1; if(SegmentTree[node].tag == true) { SegmentTree[2 * node + 1].lnc = SegmentTree[node].lnc; SegmentTree[2 * node + 2].lnc = SegmentTree[node].lnc; SegmentTree[2 * node + 1].tag = true; SegmentTree[2 * node + 2].tag = true; SegmentTree[2 * node + 1].value = http://www.mamicode.com/(SegmentTree[2 * node + 1].right - SegmentTree[2 * node + 1].left + 1) * SegmentTree[2 * node + 1].lnc; SegmentTree[2 * node + 2].value = http://www.mamicode.com/(SegmentTree[2 * node + 2].right - SegmentTree[2 * node + 2].left + 1) * SegmentTree[2 * node + 2].lnc; SegmentTree[node].lnc = 0; SegmentTree[node].tag = false; } if(data1 > m) //都在右子树 { getRangeNum(2 * node + 2, data1, data2); } else if(data2 <= m) //都在左子树 { getRangeNum(2 * node + 1, data1, data2); } else { getRangeNum(2 * node + 1, data1, m); getRangeNum(2 * node + 2, m + 1, data2); }}int main(){ int count = 0; int N; //一共有多少组数据 int OperateNum = 0; int cmd; scanf("%d", &N); while(N--) { scanf("%d", Num + count++); } build(0, 0, count - 1); scanf("%d", &OperateNum); while(OperateNum--) { scanf("%d",&cmd); if(cmd == 0) //询问 { int l, r; scanf("%d %d", &l, &r); sum = 0; getRangeNum(0, l - 1, r - 1); printf("%d\n",sum); } else if(cmd == 1)//更改 { int l, r, newP; scanf("%d %d %d", &l, &r, &newP); updateTree(0, l - 1, r - 1, newP); } } return 0;}
感叹一下，自己的编程能力着实是捉急啊...一共68个人提交，我排倒数......郁闷啊
【hihoCoder】第20周 线段树
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。