简单线段树过程详解

#include<iostream> //——————————>debug 了一上午才把这个程序运行的过程在脑子里有了思路 #include<string.h> //头文件就不多说了 #include<stdlib.h> #define maxsize 10000 //这个可定义其他数----------->这个 主要是控制数组的大小， using namespace std; struct node { //结构体 ，相当于创建的二叉树 int left, right; //记录的左右子节点 int lazy, sum; //lazy记录延迟，sum记录在这个节点的左右端点之间的总和 int mid() { return (left + right) / 2; } }T[maxsize<<2];//相当于扩大了4倍----------------------->这个时学过数据结构的都知道度为0的比度为2的多1有n个数说明n个叶子节点要建立2*n-1个点但是 //因为假若数据相对较大，则访问到了最后一行，则可能用到 n<<1 这种情况就会越界会re所以开4倍 void pushup(int rt) //向上更新sum的值 { T[rt].sum = T[rt << 1].sum + T[rt << 1 | 1].sum; } void pushdown(int rt, int m) //向下更新lazy和sum的值，主意好区间，因为整篇都是做区间的多于右区间 { if (T[rt].lazy) { T[rt << 1].lazy += T[rt].lazy; T[rt << 1 | 1].lazy += T[rt].lazy; //更新lazy值 T[rt<<1].sum += T[rt].lazy*(m - (m >> 1));//这说明如果是n为奇数 则左半部分就是多1 T[rt<<1|1].sum += T[rt].lazy *(m >> 1);//注意>>的优先级 T[rt].lazy = 0; //不能忘了把这个标志置为0 } } void create(int rt, int l, int r) { T[rt].left = l; //创建时对左节点和右节点进行赋值 T[rt].right = r; T[rt].lazy = 0; if (T[rt].left == T[rt].right) //不能写下边了，且只有当到也叶子节点时也就是当节点的左边等于右边时才赋值 { //不然地址就错了 ，因为递归调用返回时输入值的地址i就是错的 cin >> T[rt].sum; //或是赋值为0， return; } create(rt << 1, l, T[rt].mid()); //这个创建进过摸你可以看出如果n为奇数返回的中间值时中间的奇数，则说明创建的时候左边可能比右边的多 create(rt << 1 | 1, T[rt].mid()+1, r); //不能忘记mid（）+1 pushup(rt); //创建完之后别忘了向上传递更新上边的sum值 } void Union(int rt, int l, int r, int c)//rt 为根节点，在l和r的范围内部的数都加上c { if (T[rt].left == l&&T[rt].right == r) //这里就用到lazy做延迟了，这个节点lazy记录的是这个区间内要加的但是不向下进行了， { //就省了时间，sum记录的是这个姐弟啊你左右端点内的所有要加的值的和 T[rt].lazy += c; T[rt].sum += c*(T[rt].right - T[rt].left + 1); // return; } if (T[rt].left == T[rt].right) return; pushdown(rt, T[rt].right - T[rt].left + 1); if (r <= T[rt].mid()) //因为如果为奇数，则返回的中间值时中间的奇数， Union(rt << 1, l, r, c); else if (l > T[rt].mid()) Union(rt << 1 | 1, l, r, c); else { Union(rt << 1, l, T[rt].mid(), c); Union(rt << 1 | 1, T[rt].mid()+1, r, c); } pushup(rt); //这个是向上更新，其实就是用下边的两个点来更新这个点 } int sum(int rt, int l, int r)//求出在某个范围l到r内的和 { int ans=0; if (T[rt].left == l&&T[rt].right==r) //看好代码别写错了 return T[rt].sum; pushdown(rt, T[rt].right - T[rt].left + 1); if (r <= T[rt].mid()) /这个必须是小于等于因为 若是奇数则返回的时中间的奇数则就是返回的数比另一半多1，所以就小于等于 ans+=sum(rt << 1, l, r); else if (l >T[rt].mid()) ans+=sum(rt << 1 | 1, l, r); else { ans+=sum(rt << 1, l, T[rt].mid()); ans+=sum(rt << 1 | 1, T[rt].mid()+1, r);//不要忘记是mid()+1; } return ans; } int main() { int n, m, a, b, c; while (cin >> n >> m) { create(1,1,n); while (m--) { char s; cin >> s; if (s == 'Q') //查询在a，b区间的总和 { cin >> a >> b; cout << sum(1, a, b)<<endl; } else if(s=='B'){ //在 a，b区间内每个节点都加上c cin >> a >> b >> c; Union(1, a, b, c); } } } }