线段树(Segment Tree)

阅读本文基础知识:二分思想,二叉树,位运算。

本文适用于解决Luogu P3372

代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
using namespace std;
typedef long long ll;
ll ans[1000010],tag[1000010],a[1000010],n,m;
//ans为各节点保存值,tag为各节点的lazy标记,a为各节点初始值
inline ll ls(ll p){
return p<<1;//求左儿子的编号
}
inline ll rs(ll p){
return p<<1|1;//求右儿子的编号
}
inline void push_up(ll p){
ans[p]=ans[ls(p)]+ans[rs(p)];//更新p的保存值为p的左儿子保存值加上p的右儿子保存值
}
void build(ll p,ll l,ll r){
tag[p]=0;//初始化lazy标记
if(l==r)//递归边界
{
ans[p]=a[l];//初始化p的保存值
return;
}
ll mid=(l+r)>>1;
build(ls(p),l,mid);//构建左子树
build(rs(p),mid+1,r);//构建右子树
push_up(p);//求和,作为p的保存值
}
inline void f(ll p,ll l,ll r,ll k){
ans[p]+=k*(r-l+1);//更新p的保存值为原值加上该区间长度乘以变化量
tag[p]+=k;//更新lazy标记
}
inline void push_down(ll p,ll l,ll r){
ll mid=(l+r)>>1;
f(ls(p),l,mid,tag[p]);
f(rs(p),mid+1,r,tag[p]);
tag[p]=0;//重置lazy标记
}
void update(ll x,ll y,ll l,ll r,ll p,ll k){
if(x<=l&&r<=y)//递归边界
{
ans[p]+=k*(r-l+1);//更新p的保存值为原值加上该区间长度乘以变化量
tag[p]+=k;//更新lazy标记
return;
}
push_down(p,l,r);//下放lazy标记
ll mid=(l+r)>>1;
if(x<=mid) update(x,y,l,mid,ls(p),k);//如果所求区间左端点小于当前区间中点,则所求区间与当前区间的左半区间仍然有重叠,需要更新左子树
if(y>mid) update(x,y,mid+1,r,rs(p),k);//若...(参照左子树说明),更新右子树
push_up(p);//求和
}
ll query(ll x,ll y,ll l,ll r,ll p){
ll tmp=0,mid=(l+r)>>1;
if(x<=l&&r<=y) return ans[p];//递归边界
push_down(p,l,r);//下放lazy标记
if(x<=mid) tmp+=query(x,y,l,mid,ls(p));//若...(参照update里的说明),对左子树求和
if(y>mid) tmp+=query(x,y,mid+1,r,rs(p));//同上,对右子树求和
return tmp;
}
int main()
{
ll x,y,k,t;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);//建树
while(m--)
{
scanf("%lld",&t);
switch(t)
{
case 1:
{
scanf("%lld %lld %lld",&x,&y,&k);
update(x,y,1,n,1,k);//更新
break;
}
case 2:
{
scanf("%lld %lld",&x,&y);
printf("%lld\n",query(x,y,1,n,1));//求值
break;
}
}
}
return 0;
}

对于递归边界的说明:

  1. l==r

    我们在build函数中,用[l,r]表示一段区间,显然l==r时该区间内只有一个元素,故可以直接返回。所以此处以l==r作为递归边界。

  2. x<=l&&r<=y

    在此种情况中,[x,y]表示所求区间,[l,r]表示当前通过递归来到的区间。若满足x<=l&&r<=y,则表示[l,r]完全包含于[x,y]内部,此时不论如何二分递归[l,r],子区间都是完全包含于[x,y]内部的,故可以直接返回。所以此处以x<=l&&r<=y作为递归边界。

给萌新看的代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
#include<iostream>
#include<cstdio>
#include<vector>
#include<queue>
using namespace std;
long long ans[1000010],tag[1000010],a[1000010],n,m;
long long ls(long long p){
return p*2;
}
long long rs(long long p){
return p*2+1;
}
void push_up(long long p){
ans[p]=ans[ls(p)]+ans[rs(p)];
}
void build(long long p,long long l,long long r){
tag[p]=0;
if(l==r)
{
ans[p]=a[l];
return;
}
long long mid=(l+r)/2;
build(ls(p),l,mid);
build(rs(p),mid+1,r);
push_up(p);
}
void f(long long p,long long l,long long r,long long k){
ans[p]+=k*(r-l+1);
tag[p]+=k;
}
void push_down(long long p,long long l,long long r){
long long mid=(l+r)/2;
f(ls(p),l,mid,tag[p]);
f(rs(p),mid+1,r,tag[p]);
tag[p]=0;
}
void update(long long x,long long y,long long l,long long r,long long p,long long k){
if(x<=l&&r<=y)
{
ans[p]+=k*(r-l+1);
tag[p]+=k;
return;
}
push_down(p,l,r);
long long mid=(l+r)/2;
if(x<=mid) update(x,y,l,mid,ls(p),k);
if(y>mid) update(x,y,mid+1,r,rs(p),k);
push_up(p);
}
long long query(long long x,long long y,long long l,long long r,long long p){
long long tmp=0,mid=(l+r)/2;
if(x<=l&&r<=y) return ans[p];
push_down(p,l,r);
if(x<=mid) tmp+=query(x,y,l,mid,ls(p));
if(y>mid) tmp+=query(x,y,mid+1,r,rs(p));
return tmp;
}
int main()
{
long long x,y,k,t;
cin>>n>>m;
for(int i=1;i<=n;i++) scanf("%lld",&a[i]);
build(1,1,n);
while(m--)
{
scanf("%lld",&t);
switch(t)
{
case 1:
{
scanf("%lld %lld %lld",&x,&y,&k);
update(x,y,1,n,1,k);
break;
}
case 2:
{
scanf("%lld %lld",&x,&y);
printf("%lld\n",query(x,y,1,n,1));
break;
}
}
}
return 0;
}

--It's the end.Thanks for your read.--