线段树(区间查询,区间修改)——标记永久化版

传送门:https://www.luogu.org/problem/P3372

为了不下传add的标记,改为在询问的过程当中计算每个遇到的节点对当前询问的影响。而为了保证询问的复杂度,子节点的影响需要在修改操作时计算好。因此实际上,add的值表示这个区间共同加上的值,seg表示这个区间内除了add之外其它数的值的和。需要注意,区间的add值可能有一部分在祖先节点上,这在递归时累加即可。

 1 #include<bits/stdc++.h> 
 2 using namespace std;
 3 long long n,m;
 4 long long num[500009]; 
 5 long long seg[500009];//线段树上除了add之外的值 
 6 long long add[500009];//当前区间共同加上的值 
 7 inline long long read()
 8 {
 9     long long x=0,f=1;char ch=getchar();
10     while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
11     while(ch>='0'&&ch<='9'){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}
12     return x*f;
13 }
14 inline long long ls(long long x){return x<<1;}//左儿子 
15 inline long long rs(long long x){return x<<1|1;}//右儿子 
16 void build(long long now/*现在所在的节点*/,long long l,long long r/*它所在的原数列区间*/)
17 {
18     if(l==r)
19     {
20         seg[now]=num[l];
21         return;
22     }
23     long long mid=(l+r)>>1;
24     build(ls(now),l,mid);              //建立左儿子 
25     build(rs(now),mid+1,r);            //建立右儿子 
26     seg[now]=seg[ls(now)]+seg[rs(now)];//当前节点为其左右儿子的值之和 
27 }
28 void modify(long long now/*当前节点*/,long long l,long long r/* 当前区间[l,r] */,long long x,long long y,long long v)//给定区间[x,y]所有数加上v 
29 {
30     if(x<=l&&y>=r)/*如果给定区间包含当前区间就更新*/
31     {
32         add[now]+=v;/*加上这个区间共同的值*/
33         return;
34     }
35     seg[now]+=(min(r,y)-max(l,x)+1)*v;//计算子节点对当前节点的影响 
36     long long mid=(l+r)>>1;
37     if(x<=mid)modify(ls(now),l,mid,x,y,v);
38     if(mid<y)modify(rs(now),mid+1,r,x,y,v);
39 }
40 long long query(long long now,long long l,long long r,long long x,long long y)//询问区间[x,y]的和 
41 {
42     if(l>=x&&r<=y)return seg[now]+(r-l+1)*add[now];//加上这个区间的应当加上的add的值 
43     long long mid=(l+r)>>1;
44     long long res=(min(r,y)-max(l,x)+1)*add[now];  //计算标记的影响 
45     if(x<=mid)res+=query(ls(now),l,mid,x,y);       //计算左节点的贡献 
46     if(mid<y)res+=query(rs(now),mid+1,r,x,y);      //计算右节点的贡献 
47     return res;
48 }
49 int main()
50 {
51     n=read(),m=read();
52     for(long long i=1;i<=n;i++)
53     {
54         num[i]=read();
55     }
56     build(1,1,n);//建立线段树 
57     for(int i=1;i<=m;i++)
58     {
59         int pan=read();
60         if(pan==1)
61         {
62             int a=read(),b=read(),c=read();
63             modify(1,1,n,a,b,c);
64         }
65         if(pan==2)
66         {
67             long long a=read(),b=read();
68             cout<<query(1,1,n,a,b)<<endl;
69         }
70     }
71 }

 

上一篇:洛谷P2146 [NOI2015]软件包管理器 题解 树链剖分+线段树


下一篇:Codeforces Round #321 (Div. 2)