本来打算把大白书第三章一口气攻下来的，但是这个线段树也是卡了好久。
不敢过题太快，怕自己走马观花到头来结果什么都不会。
可也不能再拖了，在做题中也许有更多的体会。
模板一：
1 L R v 表示区间[L, R]所有元素都加上v
2 L R 表示查询区间[L, R]的sum, min, max
sumv[o]的定义为：如果只执行节点o及其子孙节点的中的add操作，节点o对应区间中所有数之和
1 //线段树区间修改
2 //1 L R v 表示区间[L, R]所有元素都加上v
3 //2 L R 表示查询区间[L, R]的sum, min, max
4 //sumv[o]的定义为：如果只执行节点o及其子孙节点的中的add操作，节点o对应区间中所有数之和
5 #include <cstdio>
6 #include <cstring>
7 #include <algorithm>
8 using namespace std;
9
10 const int maxnode = 1 << 17;
11
12 int _sum, _min, _max, op, qL, qR, v;
13
14 struct IntervalTree
15 {
16 int sumv[maxnode], minv[maxnode], maxv[maxnode], addv[maxnode];
17
18 //维护信息
19 void maintain(int o, int L, int R)
20 {
21 int lc = o*2, rc = o*2+1;
22 if(R > L)
23 {
24 sumv[o] = sumv[lc] + sumv[rc];
25 minv[o] = min(minv[lc], minv[rc]);
26 maxv[o] = max(maxv[lc], maxv[rc]);
27 }
28 if(addv[o]) { minv[o] += addv[o]; maxv[o] += addv[o]; sumv[o] += addv[o] * (R-L+1); }
29 }
30
31 void update(int o, int L, int R)
32 {
33 int lc = o*2, rc = o*2+1;
34 if(qL <= L && R <= qR) addv[o] += v;
35 else
36 {
37 int M = (L + R) / 2;
38 if(qL <= M) update(lc, L, M);
39 if(qR > M) update(rc, M+1, R);
40 }
41 maintain(o, L, R);
42 }
43
44 void query(int o, int L, int R, int add)
45 {
46 if(qL <= L && R <= qR)
47 {
48 _sum += sumv[o] + add * (R-L+1);
49 _min = min(_min, minv[o] + add);
50 _max = max(_max, maxv[o] + add);
51 }
52 else
53 {
54 int M = (L + R) / 2;
55 if(qL <= M) query(o*2, L, M, add + addv[o]);
56 if(qR > M) query(o*2+1, M+1, R, add + addv[o]);
57 }
58 }
59 }tree;
60
61 const int INF = 1000000000;
62
63 int main()
64 {
65 int n, m;
66 while(scanf("%d%d", &n, &m) == 2)
67 {
68 memset(&tree, 0, sizeof(tree));
69 while(m--)
70 {
71 scanf("%d%d%d", &op, &qL, &qR);
72 if(op == 1) { scanf("%d", &v); tree.update(1, 1, n); }
73 else
74 {
75 _sum = 0; _min = INF; _max = -INF;
76 tree.query(1, 1, n, 0);
77 printf("%d %d %d\n", _sum, _min, _max);
78 }
79 }
80 }
81
82 return 0;
83 }
代码君
模板二：
线段树区间修改set
1 L R v 表示将区间[L, R]全部赋值为v (v >= 0)
2 L R 表示查询区间[L, R]的sum, min, max
1 //线段树区间修改set
2 // 1 L R v 表示将区间[L, R]全部赋值为v (v >= 0)
3 // 2 L R 表示查询区间[L, R]的sum, min, max
4 #include <cstdio>
5 #include <cstring>
6 #include <algorithm>
7 using namespace std;
8
9 const int maxnode = 1 << 17;
10
11 int _sum, _min, _max, op, qL, qR, v;
12
13 struct IntervalTree
14 {
15 int sumv[maxnode], minv[maxnode], maxv[maxnode], setv[maxnode];
16
17 //维护信息
18 void maintain(int o, int L, int R)
19 {
20 int lc = o*2, rc = o*2;
21 if(R > L)
22 {
23 sumv[o] = sumv[lc] + sumv[rc];
24 minv[o] = min(minv[lc], minv[rc]);
25 maxv[o] = max(maxv[lc], maxv[rc]);
26 }
27 if(setv[o] >= 0) { minv[o] = maxv[o] = setv[o]; sumv[o] = (R-L+1) * setv[o]; }
28 }
29
30 //标记传递
31 void pushdown(int o, int L, int R)
32 {
33 int lc = o*2, rc = o*2+1;
34 if(setv[o] >= 0)//-1表示没有标记过节点
35 {
36 setv[lc] = setv[rc] = setv[o];
37 setv[o] = -1;//清除本节点的标记
38 }
39 }
40
41 void update(int o, int L, int R)
42 {
43 int lc = o*2, rc = o*2+1;
44 if(qL <= L && R <= qR) setv[o] = v;
45 else
46 {
47 pushdown(o, L, R);
48 int M = (L + R) / 2;
49 if(qL <= M) update(lc, L, M); else maintain(lc, L, M);
50 if(qR > M) update(rc, M+1, R); else maintain(rc, M+1, R);
51 }
52 maintain(o, L, R);
53 }
54
55 void query(int o, int L, int R)
56 {
57 if(setv[o] >= 0)//递归边界1：有set标记
58 {
59 _sum += setv[o] * (min(R, qR) - max(L, qL) + 1);
60 _min = min(_min, setv[o]);
61 _max = max(_max, setv[o]);
62 }
63 else if(qL <= L && R <= qR)
64 {//递归边界2：边界区间，此区间没有收到set影响
65 _sum += sumv[o];
66 _min = min(_min, minv[o]);
67 _max = max(_max, maxv[o]);
68 }
69 else
70 {//递归统计
71 int M = (L + R) / 2;
72 if(qL <= M) query(o*2, L, M);
73 if(qR > M) query(o*2+1, M+1, R);
74 }
75 }
76 }tree;
77
78 const int INF = 1000000000;
79
80 int main()
81 {
82 int n, m;
83 while(scanf("%d%d", &n, &m) == 2)
84 {
85 memset(&tree, 0, sizeof(tree));
86 memset(tree.setv, -1, sizeof(tree.setv));
87 tree.setv[0] = 1;
88 while(m--)
89 {
90 scanf("%d%d%d", &op, &qL, &qR);
91 if(op == 1) { scanf("%d", &v); tree.update(1, 1, n); }
92 else
93 {
94 _sum = 0; _min = INF; _max = -INF;
95 tree.query(1, 1, n);
96 printf("%d %d %d\n", _sum, _min, _max);
97 }
98 }
99 }
100
101 return 0;
102 }
代码君
转载于:https://www.cnblogs.com/AOQNRMGYXLMV/p/4382515.html
