首页 > 代码库 > [模板]洛谷T3372 线段树 模板1
[模板]洛谷T3372 线段树 模板1
变量定义：
sum[]：线段树节点对应区间的元素总和；
addv[]：线段树节点对应区间的所有元素的待追加值（懒标记），初值全部设为0。
过程说明：
建树（Build）：
若当前节点仅包含原序列中的一个值，即L=R，则直接赋值为序列中该值，否则递归建立左右子树后，将左右子树保存的sum值相加，即得到当前节点的sum值。
懒标记下放（Push_down）：
将当前节点的addv值下放到左右子树。
细节实现：
1.子树的addv值加上当前节点的addv值；
2.子树的sum值加上（子树包含元素数量*当前节点的addv值）；
3.清空当前节点的addv值，即赋值为0。
特别说明：
1.使用前判断，若当前节点的addv值为0则不需执行此下放函数。虽然执行了也不会有影响，但浪费时间。
2.为尽量节省时间，要将判断放在此函数外而不是函数内。
区间加（update）：
若当前节点完全包含在待更新区间内，则直接修改当前节点的addv值和sum值即可；
否则：
1.若当前节点addv值非0，则进行懒标记下放；
2.若待更新区间与左子树对应区间有交集，则递归更新左子树，同理对右子树也执行类似操作。
3.递归更新子树完成后，重新计算当前节点的sum值。
区间查询（query）：
若当前节点完全包含在待查询区间内，则直接返回当前节点的sum值；
否则：
1.定义当前节点结果ans=0；
2.若当前节点addv值非0，则进行懒标记下放；
3.若待查询区间与左子树对应区间有交集，则递归查询左子树，并将所得结果加给ans，同理对右子树也执行类似操作。
4.递归查询子树完成后，返回计算好的ans值。
代码如下：
1 #include<cstdio> 2 #include<iostream> 3 #include<cstring> 4 #include<ctime> 5 #include<cstdlib> 6 #include<cmath> 7 #include<algorithm> 8 #include<string> 9 #include<stack> 10 #include<queue> 11 #include<vector> 12 #include<map> 13 using namespace std; 14 long long c[2000010]; 15 struct sgt{ 16 long long sum[2000010]; 17 long long addv[2000010]; 18 void build(int o,int l,int r){ 19 addv[o]=0; 20 if(l==r)sum[o]=c[l]; 21 else{ 22 int mid=(l+r)>>1; 23 int lson=o<<1; 24 int rson=lson|1; 25 build(lson,l,mid); 26 build(rson,mid+1,r); 27 sum[o]=sum[lson]+sum[rson]; 28 } 29 } 30 void push_down(int o,int l,int r,int mid,int lson,int rson){ 31 addv[lson]+=addv[o]; 32 addv[rson]+=addv[o]; 33 sum[lson]+=(mid-l+1)*addv[o]; 34 sum[rson]+=(r-mid)*addv[o]; 35 addv[o]=0; 36 } 37 void update(int o,int l,int r,int a,int b,int x){ 38 if(l>=a && r<=b){ 39 addv[o]+=x; 40 sum[o]+=(r-l+1)*x; 41 return; 42 } 43 else{ 44 int mid=(l+r)>>1; 45 int lson=o<<1; 46 int rson=lson|1; 47 if(addv[o])push_down(o,l,r,mid,lson,rson); 48 if(a<=mid)update(lson,l,mid,a,b,x); 49 if(b>mid)update(rson,mid+1,r,a,b,x); 50 sum[o]=sum[lson]+sum[rson]; 51 } 52 } 53 long long query(int o,int l,int r,int a,int b){ 54 if(l>=a && r<=b)return sum[o]; 55 else{ 56 int mid=(l+r)>>1; 57 int lson=o<<1; 58 int rson=lson|1; 59 long long ans=0; 60 if(addv[o])push_down(o,l,r,mid,lson,rson); 61 if(a<=mid)ans+=query(lson,l,mid,a,b); 62 if(b>mid)ans+=query(rson,mid+1,r,a,b); 63 return ans; 64 } 65 } 66 }; 67 sgt tree; 68 int n,m,i,f; 69 int x,y,k; 70 int main(){ 71 scanf("%d%d",&n,&m); 72 for(i=1;i<=n;i++)scanf("%d",&c[i]); 73 tree.build(1,1,n); 74 for(i=1;i<=m;i++){ 75 scanf("%d",&f); 76 if(f&1){ 77 scanf("%d%d%d",&x,&y,&k); 78 tree.update(1,1,n,x,y,k); 79 } 80 else{ 81 scanf("%d%d",&x,&y); 82 printf("%lld\n",tree.query(1,1,n,x,y)); 83 } 84 } 85 return 0; 86 }
[模板]洛谷T3372 线段树 模板1
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。