线段树基础求和与修改

胡乱分析

说到线段树实际上还是一个具有叫做lazy tag的完全二叉树

分布操作

建树

建树操作需要知道一个就是当前p的左儿子是2p右儿子是2p+1然后我们递归建树即可,回溯的时候更新每个值
所以代码就比较清晰了,如果当前l=r的话那么我们就把这个叶子节点赋值然后向上回溯即可

1
2
3
4
5
6
7
8
9
10
11
12
13
void build(int p,int l,int r)
{
t[p].l=l;t[p].r=r;
if(l==r)
{
t[p].sum=num[l];
return;
}
int mid=(l+r)>>1;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
t[p].sum=t[2*p].sum+t[2*p+1].sum;
}

lazy tag下放

lazy tag在这里是记录区间总共更改了多少,下放的时候要注意更改左右儿子的值并且把左右儿子的lazy tag更新,自己的lazy tag清除

1
2
3
4
5
6
7
8
9
10
11
void lazy(int p)
{
if(t[p].tag)
{
t[2*p].sum+=t[p].tag*(t[2*p].r+1-t[2*p].l);
t[2*p+1].sum+=t[p].tag*(t[2*p+1].r+1-t[2*p+1].l);
t[2*p].tag+=t[p].tag;
t[2*p+1].tag+=t[p].tag;
t[p].tag=0;
}
}

更改操作

更改是把父节点对应的子节点的个数乘以修改的值,因为每个节点都加上一个数,所以一次把加和给父节点,并且给父节点打上lazy tag,如果修改的区间并不覆盖父节点所管理的范围,那么下放lazy tag并且递归更改其他区间,最后回溯赋值

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
void change(int p,int x,int y,int z)
{
if(t[p].l>=x&&t[p].r<=y)
{
t[p].sum+=1LL*z*(t[p].r+1-t[p].l);
t[p].tag+=z;
return;
}
lazy(p);
int mid=(t[p].r+t[p].l)>>1;
if(x<=mid)
change(p*2,x,y,z);
if(y>mid)
change(p*2+1,x,y,z);
t[p].sum=t[2*p].sum+t[2*p+1].sum;
}

查询

查询需要看当前是不是已经区间覆盖了,如果是那么返回当前的区间的值,否则还是下放lazy tag进行递归寻找

1
2
3
4
5
6
7
8
9
10
11
12
13
long long sum(int p,int x,int y)
{
if(t[p].l>=x&&t[p].r<=y)
return t[p].sum;
lazy(p);
int mid=(t[p].r+t[p].l)>>1;
long long ans=0;
if(x<=mid)
ans+=sum(2*p,x,y);
if(y>mid)
ans+=sum(2*p+1,x,y);
return ans;
}

完整模板(洛谷P3372 【模板】线段树 1)

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
86
#include <bits/stdc++.h>
using namespace std;
struct node
{
long long l,r,sum,tag;
}t[666666];
long long num[666666];
void build(int p,int l,int r)
{
t[p].l=l;t[p].r=r;
if(l==r)
{
t[p].sum=num[l];
return;
}
int mid=(l+r)>>1;
build(2*p,l,mid);
build(2*p+1,mid+1,r);
t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
void lazy(int p)
{
if(t[p].tag)
{
t[2*p].sum+=t[p].tag*(t[2*p].r+1-t[2*p].l);
t[2*p+1].sum+=t[p].tag*(t[2*p+1].r+1-t[2*p+1].l);
t[2*p].tag+=t[p].tag;
t[2*p+1].tag+=t[p].tag;
t[p].tag=0;
}
}
void change(int p,int x,int y,int z)
{
if(t[p].l>=x&&t[p].r<=y)
{
t[p].sum+=1LL*z*(t[p].r+1-t[p].l);
t[p].tag+=z;
return;
}
lazy(p);
int mid=(t[p].r+t[p].l)>>1;
if(x<=mid)
change(p*2,x,y,z);
if(y>mid)
change(p*2+1,x,y,z);
t[p].sum=t[2*p].sum+t[2*p+1].sum;
}
long long sum(int p,int x,int y)
{
if(t[p].l>=x&&t[p].r<=y)
return t[p].sum;
lazy(p);
int mid=(t[p].r+t[p].l)>>1;
long long ans=0;
if(x<=mid)
ans+=sum(2*p,x,y);
if(y>mid)
ans+=sum(2*p+1,x,y);
return ans;
}
int main()
{
ios::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int n,m;
cin>>n>>m;
for(int i=1;i<=n;i++)
cin>>num[i];
build(1,1,n);
while(m--)
{
int p,x,y,z;
cin>>p;
if(p==1)
{
cin>>x>>y>>z;
change(1,x,y,z);
}
else
{
cin>>x>>y;
cout<<sum(1,x,y)<<"\n";
}
}
}
就算是一分钱,也是对作者极大的支持
------ 本文结束 ------

版权声明

Baccano by baccano is licensed under a Creative Commons BY-NC-ND 4.0 International License.
baccano创作并维护的Baccano博客采用创作共用保留署名-非商业-禁止演绎4.0国际许可证
本文首发于baccano 博客( http://baccano.fun ),版权所有,侵权必究。

小游戏

---小游戏:要不要来选择一下自己可能的老婆?---

简易发声器

---简易的七键钢琴插件---

可以使用鼠标点击琴键也可以使用主键盘1-7或者小键盘的1-7来操作

那么现在开始吧

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
0%