线段树是一种灵活的数据结构,可以修改的地方在子区间的合并对当前区间的影响

单点修改,区间查询

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
const int maxn = 500010;
struct Node
{
int sum,mx,mn;
} p[maxn<<2];

void pushup(int u) //向上更新
{
p[u].sum = p[u<<1].sum + p[u<<1|1].sum;
p[u].mx = max(p[u<<1].mx , p[u<<1|1].mx);
p[u].mn = min(p[u<<1].mn , p[u<<1|1].mn);
}

void build(int L,int R,int u) //自底向上建树
{
if(L==R)
{
int x;
scanf("%d",&x);
p[u].sum = Node.mx = p[u].mn = x;
}
int m = (L+R)>>1;
build(L,m,u<<1);
build(m+1,R,u<<1|1);
pushup(u);
}

void update(int p,int v,int L,int R,int u)
{
if(L==R)
{
p[u].sum = p[u].mx = p[u].mn = v;
return;
}
else
{
int m = (L+R)>>1;
if(p<=m) update(p,v,L,m,u<<1);
else update(p,v,m+1,R,u<<1|1);
pushup(u);
}
}

Node query(int cL,int cR,int L,int R,int u)
{
if(cL <= L && R <= cR) return p[u];
int m=(L+R)>>1;
if(m>=cL && m>=cR)
{
return query(cL,cR,L,m,u<<1);
}
else if(m<cL && m<cR)
{
return query(cL,cR,m+1,R,u<<1|1);
}
else
{
Node a = query(cL,cR,L,m,u<<1);
Node b = query(cL,cR,m+1,R,u<<1|1);
Node res;
res.sum = a.sum+b.sum;
res.mx = max(a.mx,b.mx);
res.mn = min(a.mn,b.mn);
return res;
}
}

区间修改,区间查询

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
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;

const int maxn = 10010;
const int INF = 0x3f3f3f3f;
struct Node
{
int sum;
int mx,mn;
int cnt;
};

Node p[maxn<<2];

void pushdown(int u) //下传
{
p[u<<1].cnt += p[u].cnt;
p[u<<1|1].cnt += p[u].cnt;
p[u].cnt = 0;
}

void pushup(int L,int R,int u) //向上更新
{
int m = (L+R)>>1;
p[u].sum = p[u<<1].cnt*(m-L+1)+p[u<<1].sum + p[u<<1|1].cnt*(R-m) + p[u<<1|1].sum;
p[u].mx = max(p[u<<1].cnt + p[u<<1].mx,p[u<<1|1].cnt + p[u<<1|1].mx);
p[u].mn = min(p[u<<1].cnt + p[u<<1].mn,p[u<<1|1].cnt + p[u<<1|1].mn);
}

void build(int L,int R,int u) //自底向上建树
{
p[u].sum = p[u].mx = p[u].mn = p[u].cnt = 0;
if(L==R)
{
int x;
scanf("%d",&x);
p[u].sum = p[u].mx = p[u].mn = x;
}
else
{
int m = (L+R)>>1;
build(L,m,u<<1);
build(m+1,R,u<<1|1);
pushup(L,R,u);
}
}

void update(int cL,int cR,int val,int L,int R,int u)
{
if(cL <= L && R<= cR)
{
p[u].cnt += val;
}
else
{
pushdown(u);
int m = (L+R)>>1;
if(m>=cL) update(cL,cR,val,L,m,u<<1);
if(m<cR) update(cL,cR,val,m+1,R,u<<1|1);
pushup(L,R,u);
}
}

Node query(int cL,int cR,int L,int R,int u)
{
if(cL<= L && R<=cR)
{
Node res;
res.sum = p[u].sum + (R-L+1)*p[u].cnt;
res.mx = p[u].mx + p[u].cnt;
res.mn = p[u].mn + p[u].cnt;
return res;
}
else
{
Node res;
pushdown(u);
int m = (L+R)>>1;
if(m>=cL && m>=cR)
{
res = query(cL,cR,L,m,u<<1);
}
else if(m<cL && m<cR)
{
res = query(cL,cR,m+1,R,u<<1|1);
}
else
{
Node a = query(cL,cR,L,m,u<<1);
Node b = query(cL,cR,m+1,R,u<<1|1);
res.sum = a.sum + b.sum;
res.mx = max(a.mx,b.mx);
res.mn = min(a.mn,b.mn);
}
pushup(L,R,u);
return res;
}
}


int main()
{
//freopen("test.txt","r",stdin);
int n;
while(scanf("%d",&n)==1)
{
build(0,n-1,1);
Node res = query(0,n-1,0,n-1,1);
printf("%d %d %d\n",res.sum,res.mx,res.mn);
update(3,5,2,0,n-1,1);
res = query(0,n-1,0,n-1,1);
printf("%d %d %d\n",res.sum,res.mx,res.mn);
}
return 0;
}

各种姿势