算法提高之一個簡單的整數問題2

• 核心思想：線段樹

  • 懶標記：add存每個子節點需要加的數
  • pushdown：將懶標記向下存 同時清除本行懶標記

•   #include <iostream>#include <cstring>#include <algorithm>using namespace std;typedef long long LL;const int N = 100010;int n,m;int w[N];struct Node{int l,r;LL sum,add;}tr[N*4];void pushup(int u){tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;}void pushdown(int u){auto &root = tr[u],&left = tr[u<<1],&right = tr[u<<1|1];if(root.add){left.add += root.add,left.sum += (LL)(left.r - left.l + 1)*root.add;right.add += root.add,right.sum += (LL)(right.r - right.l + 1)*root.add;root.add = 0;}}void build(int u,int l,int r){if(l == r){tr[u] = {l,r,w[r],0};}else{tr[u].l = l,tr[u].r = r;int mid = l+r>>1;build(u<<1,l,mid),build(u<<1|1,mid+1,r);pushup(u);}}void modify(int u,int l,int r,int v){if(l <= tr[u].l && r >= tr[u].r){tr[u].sum += (tr[u].r - tr[u].l + 1) *v;  //長度 * 加的數tr[u].add += v;}else{pushdown(u);  //先清空本行懶標記int mid = tr[u].l + tr[u].r >> 1;if(l <= mid) modify(u<<1,l,r,v);if(r > mid) modify(u<<1|1,l,r,v); pushup(u);}}LL query(int u,int l,int r){if(l<=tr[u].l && r>=tr[u].r) return tr[u].sum;pushdown(u);int mid = tr[u].l + tr[u].r >> 1;LL v=0;if(l<=mid) v = query(u<<1,l,r);if(r > mid) v += query(u<<1|1,l,r);return v;}int main(){cin>>n>>m;for(int i=1;i<=n;i++) cin>>w[i];build(1,1,n);char op[2];int l,r,t;while(m--){cin>>op>>l>>r;if(op[0] == 'Q') cout<<query(1,l,r)<<endl;else{cin>>t;modify(1,l,r,t);}}}