线段树入门版qwq

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

1 #include
     
       2 #include
      
        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; emm27     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;//emm34     }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 }