POJ3468[A Simple Problem with Integers] 线段树基本操作

题目链接

题目大意：求一段区间和，支持区间增减操作

解题思路线段树

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
const int maxn = 1e5 + 7;
#define ls nd<<1
#define rs nd<<1|1
#define LL long long
struct Tree{LL sum, add;int l, r, flg;
}t[maxn*4];void pushup(int nd){t[nd].sum = t[ls].sum + t[rs].sum;
}void pushdown(int nd){if( t[nd].flg==1 ){t[ls].flg = t[rs].flg = t[nd].flg;t[nd].flg = 0;t[ls].add += t[nd].add;t[rs].add += t[nd].add;int mid = ( t[nd].l + t[nd].r ) >> 1;t[ls].sum += (mid-t[nd].l+1)*t[nd].add;t[rs].sum += (t[nd].r-mid)*t[nd].add;t[nd].add = 0;}
}void build( int nd, int l, int r ){t[nd].l=l, t[nd].r=r;if( l==r ){scanf("%lld", &t[nd].sum );t[nd].add=0;t[nd].flg=0;return;}int mid=(l+r)>>1;build(ls,l,mid);build(rs,mid+1,r);pushup(nd);
}void modify(int nd, int lt, int rg, int val){if( lt<= t[nd].l && t[nd].r <=rg ){t[nd].add+=(LL)val;t[nd].flg=1;t[nd].sum+=(LL)(t[nd].r-t[nd].l+1)*val;return;}pushdown(nd);int mid=(t[nd].l+t[nd].r)>>1;if( lt<=mid ) modify(ls, lt, rg, val);if( mid<rg) modify(rs, lt, rg, val);pushup(nd);
}LL query(int nd, int lt, int rg ){if( lt<=t[nd].l && t[nd].r<=rg ){return t[nd].sum;}pushdown(nd);LL cnt=0;int mid=(t[nd].l+t[nd].r)>>1;if( mid>=lt ) cnt+=query(ls,lt,rg);if( mid<rg )cnt+=query(rs,lt,rg);return cnt;
}int main(){int n, m;scanf("%d%d", &n, &m );build(1,1,n);while( m-- ){char ch[2];scanf("%s", ch);if( ch[0]=='Q' ){int x, y;scanf("%d%d", &x, &y );printf("%lld\n", query(1,x,y) );}else{int x, y, z;scanf("%d%d%d", &x, &y, &z);modify(1,x,y,z);}}return 0;
}