线段树 模板 小灰灰 2022-05-16 05:39 170阅读 0赞 洛谷oj:[点我][Link 1] 线段树区间修改区间查询 #include<iostream> #include<cstdio> #include<cmath> #include<algorithm> #define maxn 100007 //元素总个数 int q; long long Sum[maxn<<2]; int Add[maxn<<2];//Sum求和,Add为懒惰标记 int A[maxn],n;//存原数组数据下标[1,n] //PushUp函数更新节点信息,这里是求和 void PushUp(int rt){ Sum[rt]=Sum[rt<<1]+Sum[rt<<1|1]; } void PushDown(int rt,int ln,int rn){ //ln,rn为左子树,右子树的数字数量。 if(Add[rt]) { //下推标记 Add[rt<<1]+=Add[rt]; Add[rt<<1|1]+=Add[rt]; //修改子节点的Sum使之与对应的Add相对应 Sum[rt<<1]+=Add[rt]*ln; Sum[rt<<1|1]+=Add[rt]*rn; //清除本节点标记 Add[rt]=0; } } //Build函数建立线段树 void Build(int l,int r,int rt) { //[l,r]表示当前节点区间,rt表示当前节点的实际存储位置 if(l==r) { //若到达叶节点 Sum[rt]=A[l];//存储A数组的值 return; } int m=(l+r)>>1; //左右递归 Build(l,m,rt<<1); Build(m+1,r,rt<<1|1); //更新信息 PushUp(rt); } void Update(int L,int R,int C,int l,int r,int rt) { //L,R表示操作区间,l,r表示当前节点区间,rt表示当前节点编号 if(L <= l && r <= R) { //如果本区间完全在操作区间[L,R]以内 Sum[rt]+=C*(r-l+1);//更新数字和,向上保持正确 Add[rt]+=C;//增加Add标记,表示本区间的Sum正确,子区间的Sum仍需要根据Add的值来调整 return ; } int m=(l+r)>>1; PushDown(rt,m-l+1,r-m);//下推标记 //这里判断左右子树跟[L,R]有无交集,有交集才递归 if(L <= m) Update(L,R,C,l,m,rt<<1); if(R > m) Update(L,R,C,m+1,r,rt<<1|1); PushUp(rt);//更新本节点信息 } long long Query(int L,int R,int l,int r,int rt) { //[L,R]表示操作区间,[l,r]表示当前区间,rt:当前节点编号 if(L <= l && r <= R) { //在区间内直接返回 return Sum[rt]; } int m=(l+r)>>1; //左子区间:[l,m] 右子区间:[m+1,r] 求和区间:[L,R] //累加答案 PushDown(rt,m-l+1,r-m); long long ANS=0; if(L <= m) ANS+=Query(L,R,l,m,rt<<1);//左子区间与[L,R]有重叠,递归 if(R > m) ANS+=Query(L,R,m+1,r,rt<<1|1); //右子区间与[L,R]有重叠,递归 return ANS; } int main() { scanf("%d%d",&n,&q); for(int i=1; i<=n; i++) { scanf("%d",&A[i]); } Build(1,n,1); while(q--) { int flag,l,r,k; scanf("%d",&flag); if(flag==1) { scanf("%d%d%d",&l,&r,&k); Update(l,r,k,1,n,1); } else{ scanf("%d%d",&l,&r); long long ANS=Query(l,r,1,n,1); printf("%lld\n",ANS); } } } [Link 1]: https://www.luogu.org/problemnew/show/P3372
还没有评论,来说两句吧...