线段树 模板
1 #define MAXSIZE 50010
2
3 int tree[4*MAXSIZE]; // 此處要開4倍空間
4 int lz[4*MAXSIZE];
5
6 void init()
7 {
8 memset(tree, 0, sizeof(tree));
9 memset(lz, 0, sizeof(lz));
10 }
11
12
13 void build(int node, int l, int r)
14 {
15 if(l == r) // 到達葉子節點，賦值
16 {
17 scanf("%d", &tree[node]);
18 return;
19 }
20
21 int mid = (l+r)/2;
22 build(node*2, l, mid);
23 build(node*2+1, mid+1, r);
24
25 tree[node] = tree[node*2] + tree[node*2+1];
26 }
27
28
29 void push_down(int node, int l, int r)
30 {
31 if(lz[node])
32 {
33 int mid = (l+r)/2;
34 lz[node*2] += lz[node];
35 lz[node*2+1] += lz[node];
36 tree[node*2] += (mid-l+1)*lz[node];
37 tree[node*2+1] += (r-mid)*lz[node];
38 lz[node] = 0;
39 }
40 }
41
42 // 單點更新，node為1(從根開始)，lr為根的范圍，index為待更新的數，add為更新的增量
43 void update(int node, int l, int r, int index, int add)
44 {
45 if(l == r)
46 {
47 tree[node] += add; // 更新方式
48 return;
49 }
50
51 int mid = (l+r)/2;
52 if(index <= mid) // 進入左子樹
53 update(node*2, l, mid, index, add);
54 else // 進入右子樹
55 update(node*2+1, mid+1, r, index, add);
56
57 tree[node] = tree[node*2] + tree[node*2 + 1];
58 }
59
60 // 區間更新，lr為更新范圍，LR為線段樹范圍，add為更新值
61 void update_range(int node, int l, int r, int L, int R, int add)
62 {
63 if(l <= L && r >= R)
64 {
65 lz[node] += add;
66 tree[node] += (R-L+1)*add; // 更新方式
67 return;
68 }
69
70 push_down(node, L, R);
71 int mid = (L+R)/2;
72 if(mid >= l) // 進入左子樹
73 update_range(node*2, l, r, L, mid, add);
74 if(r > mid) // 進入右子樹
75 update_range(node*2+1, l, r, mid+1, R, add);
76
77 tree[node] = tree[node*2] + tree[node*2 + 1];
78 }
79
80 // 區間查找
81 int query_range(int node, int l, int r, int L, int R)
82 {
83 if(l <= L && r >= R)
84 return tree[node];
85 push_down(node, L, R);
86 int mid = (L+R)/2;
87 int sum = 0;
88 if(mid >= l)
89 sum += query_range(node*2, l, r, L, mid);
90 if(r > mid)
91 sum += query_range(node*2+1, l, r, mid+1, R);
92
93 return sum;
94 }
?
轉載于:https://www.cnblogs.com/FengZeng666/p/11445645.html
總結
- 上一篇： 线段树原理详解
- 下一篇： 敌兵布阵 HDU - 1166 (线段树