c/c++语言开发共享【模板】 线段树

 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("%lldn",ans);  64         }  65     }  66 }