线段树模板

 1 #define MAXSIZE 50010
 2 
 3 int tree[4*MAXSIZE];
 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 // 区间更新，lr为更新范围，LR为线段树范围，add为更新值
43 void update_range(int node, int l, int r, int L, int R, int add)
44 {
45     if(l <= L && r >= R)
46     {
47         lz[node] += add;
48         tree[node] += (R-L+1)*add;    // 更新方式 
49         return;
50     }
51     
52     push_down(node, L, R);
53     int mid = (L+R)/2;
54     if(mid >= l)    // 进入左子树 
55         update_range(node*2, l, r, L, mid, add);
56     if(r > mid)        // 进入右子树 
57         update_range(node*2+1, l, r, mid+1, R, add);
58         
59     tree[node] = tree[node*2] + tree[node*2 + 1]; 
60 }
61 
62 // 区间查找 
63 int query_range(int node, int l, int r, int L, int R)
64 {
65     if(l <= L && r >= R)
66         return tree[node];
67     push_down(node, L, R);
68     int mid = (L+R)/2;
69     int sum = 0;
70     if(mid >= l)
71         sum += query_range(node*2, l, r, L, mid);
72     if(mid < r)
73         sum += query_range(node*2+1, l, r, mid+1, R);
74     
75     return sum;
76 }