首页 > > 程序设计 > C/C++ >

【模板】线段树

2018-09-01 05:38:28来源：博客园阅读 ()

洛谷P3372

线段树入门版qwq

区间查询区间修改（都是加法qaq）

 1 #include<cstdio>
 2 #include<iostream>
 3 #define sz 100010
 4 #define LL long long
 5 using namespace std;
 6 int n, m, x, y, pd, add = 0;
 7 LL ans = 0;
 8 struct seg {
 9     LL l, r, w, f;
10 }tree[sz<<2];
11 void build(int k, int left, int right) {
12     tree[k].l = left, tree[k].r = right;
13     if(left == right) {
14         scanf("%d",&tree[k].w);
15         return;
16     }
17     int mid = (tree[k].l + tree[k].r)>>1;
18     build(k<<1, left, mid), build(k<<1|1, mid+1, right);
19     tree[k].w = tree[k<<1].w + tree[k<<1|1].w;
20 }
21 int down(int k) {
22     tree[k<<1].f += tree[k].f;
23     tree[k<<1|1].f += tree[k].f;
24     tree[k<<1].w += tree[k].f*(tree[k<<1].r-tree[k<<1].l+1);
25     tree[k<<1|1].w += tree[k].f*(tree[k<<1|1].r-tree[k<<1|1].l+1);
26 //    tree[k].w = tree[k<<1].w + tree[k<<1|1].w; emm
27     tree[k].f = 0;
28 }
29 void change(int k) {
30     if(x <= tree[k].l && y >= tree[k].r) {
31         tree[k].w += add*(tree[k].r-tree[k].l+1);
32         tree[k].f += add;
33         return;//emm
34     }
35     if(tree[k].f) down(k);
36     int mid = (tree[k].l+tree[k].r)>>1;
37     if(x <= mid) change(k<<1);
38     if(y > mid) change(k<<1|1);
39     tree[k].w = tree[k<<1].w + tree[k<<1|1].w;
40 }
41 void ask_sum(int k) {
42     if(x <= tree[k].l && y >= tree[k].r) {
43         ans += tree[k].w;
44         return;
45     }
46     if(tree[k].f) down(k);
47     int mid = (tree[k].l+tree[k].r)>>1;
48     if(x <= mid) ask_sum(k<<1);
49     if(y > mid) ask_sum(k<<1|1);
50 }
51 int main() {
52     scanf("%d%d",&n,&m);
53     build(1,1,n);
54     for(int i = 1; i <= m; i++) {
55         scanf("%d%d%d",&pd,&x,&y);
56         if(pd == 1) {
57             scanf("%d",&add);
58             change(1);
59         }
60         else {
61             ans = 0;
62             ask_sum(1);
63             printf("%lld\n",ans);
64         }
65     }
66 }