线段树模版

C++线段树模版代码

洛谷P3372 【模板】线段树 1

#include<bits/stdc++.h>
#define int long long
#define ls 2*root
#define rs 2*root+1
using namespace std;const int MAXN = 1e5+10;int he[5 * MAXN], biao[5 * MAXN], a[5 * MAXN];void pushup(int root){he[root] = he[rs]+he[ls];
}void build(int root, int l, int r){biao[root]=0;if(l == r) {he[root]=a[l];return ;} int mid = (l + r) / 2; build(ls, l, mid); build(rs, mid+1, r); pushup(root);
}void pushdown(int root,int l,int r){int mid=(l+r)/2;biao[ls]+=biao[root];he[ls]+=biao[root]*(mid-l+1);biao[rs]+=biao[root];he[rs]+=biao[root]*(r-mid);biao[root]=0;
}void update(int root, int l, int r,int ql,int qr,int k){if(ql<=l&&r<=qr){he[root]+=k*(r-l+1);biao[root]+=k;return ;}pushdown(root,l,r);int mid=(l+r)/2;if(ql<=mid)update(ls,l,mid,ql,qr,k);if(qr>mid) update(rs,mid+1,r,ql,qr,k);pushup(root);
}int query(int root, int l, int r, int qx, int qy){int ans = 0;if (qx <= l && r <= qy) return he[root];int mid=(l+r)/2;pushdown(root,l,r);if (qx <= mid) ans += query(ls, l, mid, qx, qy);if (qy > mid) ans += query(rs, mid+1, r, qx, qy);return ans;
}signed main(){int n,m;cin >> n >> m;for(int i = 1;i<=n;i++){cin >>a[i]; }build(1,1,n);while(m--){char op;int a, b,k;cin >> op >> a >> b;if(a>b)swap(a,b);if(op == '1'){cin >> k;update(1, 1, n, a, b, k);}else if(op == '2'){cout << query(1, 1, n, a, b)<<'\n';}}return 0; 
}