线段树码, 比树状数组好理解多了 (其实理解了, 都挺简单的)
就是代码贼长
// 支持操作 //
建树 Build(1,n,1);,
- // 把 1 到 n 的 a[] 建一颗线段树
- // 点更新 Add(L,C,1,n,1);//L 改成 C
- // 区间修改 Update(L,R,C,1,n,1);
- //L 到 R 的区间加上 C
- // 区间查询 int ANS=Query(L,R,1,n,1); //L 到 R 的区间和
- // 支持操作
- // 建树
- Build(1,n,1);// 把 1 到 n 的 a[] 建一颗线段树
- // 点更新
- Add(L,C,1,n,1);//L 改成 C
- // 区间修改
- Update(L,R,C,1,n,1);//L 到 R 的区间加上 C
- // 区间查询
- int ANS=Query(L,R,1,n,1); //L 到 R 的区间和
- const int MAXN=50010;
- int a[MAXN],ans[MAXN<<2],lazy[MAXN<<2];
- //a[] 为原序列信息, ans[] 模拟线段树维护区间和, lazy[] 为懒惰标记
- void PushUp(int rt) { // 更新节点信息
- ans[rt]=ans[rt<<1]+ans[rt<<1|1];
- }//rt<<1 表示左孩子, rt<<1|1 表示右孩子
- // 如果不理解可以改成 rt*2 和 rt*2+1
- //st<<1 是二进制码左移 1, 二进制, 所以就是乘 2(2^1), 相似的 <<2, 是乘 2^2, 以此类推
- //st<<1|1,st<<1 之后肯定是偶数, 毫无疑问二进制的第一位是 0, 然后 | 1 就是加 1
- void Build(int l,int r,int rt) { // 递归建树, 从 l 到 r,rt 是数组的标号
- if (l==r) {
- ans[rt]=a[l];
- return;
- }// 递归终点
- int mid=(l+r)>>1;// 这是一棵树, 分成两半
- Build(l,mid,rt<<1);// 左子树
- Build(mid+1,r,rt<<1|1);// 右子树
- PushUp(rt);
- // 更新 ans[rt]
- }
- void PushDown(int rt,int ln,int rn) { //ln 表示左子树元素结点个数, rn 表示右子树结点个数
- ///////////////////////////////// 表示不会, 不懂
- if (lazy[rt]) {
- lazy[rt<<1]+=lazy[rt];
- lazy[rt<<1|1]+=lazy[rt];
- ans[rt<<1]+=lazy[rt]*ln;
- ans[rt<<1|1]+=lazy[rt]*rn;
- lazy[rt]=0;
- }
- }
- void Add(int L,int C,int l,int r,int rt) { // 点更新
- // 把 L 号改成 C, 在 l 到 r 的区间内查询, 这玩意貌似就是二分找值
- if (l==r) { // 重合了, 就找到
- ans[rt]+=C;
- return;
- }
- int mid=(l+r)>>1;// 中间值
- PushDown(rt,mid-l+1,r-mid); // 若既有点更新又有区间更新, 需要这句话!!!dont know
- if (L<=mid)// 如果这个点小于 mid, 他肯定在左子树里
- Add(L,C,l,mid,rt<<1);
- else// 否则, 他肯定在右子树里
- Add(L,C,mid+1,r,rt<<1|1);
- PushUp(rt);// 更新节点信息
- }
- void Update(int L,int R,int C,int l,int r,int rt) { // 区间修改
- //
- if (L<=l&&r<=R) {
- ans[rt]+=C*(r-l+1);// 改变 ans[] 的值
- lazy[rt]+=C;// 懒惰标记 + C, 不必再往下更改
- return;
- }// 递归终点
- int mid=(l+r)>>1;
- PushDown(rt,mid-l+1,r-mid);
- if (L<=mid) Update(L,R,C,l,mid,rt<<1);// 如果 L 都大于 mid, 那肯定都在 mid 的
- if (R>mid) Update(L,R,C,mid+1,r,rt<<1|1);
- PushUp(rt);// 更新
- }
- LL Query(int L,int R,int l,int r,int rt) { // 区间查询
- //L 到 R 的和, 在 l 和 r 的里面找, rt 是树的标号 (在哪个数下)
- if (L<=l&&r<=R)// 如果标号正好重叠了
- return ans[rt];// 那结果就是我们事先算好的 ans
- int mid=(l+r)>>1;// 不能求出, 就分开考虑
- PushDown(rt,mid-l+1,r-mid);// 若更新只有点更新, 不需要这句!!! 不会这句话
- LL ANS=0;
- if (L<=mid) ANS+=Query(L,R,l,mid,rt<<1);// 左孩子的值
- if (R>mid) ANS+=Query(L,R,mid+1,r,rt<<1|1);// 右孩子的值
- return ANS;// 加起来的值返回
- }
线段树
来源: http://www.bubuko.com/infodetail-2587679.html