题意：中文题，不多说了。
思路：这题以前用树状数组做过，这次用的线段树，当做可参考模板。
代码：
#include #include #include #include #include #include #include #include #include #include #include #define PI acos(-1.0) #define maxn 100000 #define INF 1<<25 #define MAX 0x7fffffff typedef long long ll; using namespace std; int n,m,l,r; struct line { int left,right; int n; int value; } a [maxn*4]; void build_tree(int l,int r,int step) { a[step].left=l; a[step].right=r; a[step].n=0; if(l==r) { scanf(%d,&a[step].value); return; } int mid=(l+r)/2; build_tree(l,mid,step*2); build_tree(mid+1,r,step*2+1); a[step].value=a[step*2].value+a[step*2+1].value; } int ans; void add(int s,int t,int step,int k) { if(s==a[step].left&&t==a[step].right) { a[step].value+=k; return; } if(a[step].left==a[step].right) return; int mid=(a[step].left+a[step].right)/2; if(mid>=t) add(s,t,step*2,k); else if(mid =s&&a[step].right<=t) { ans+=a[step].value; return 0; } else { int mid=(a[step].left+a[step].right)/2; if(mid>=t) query(s,t,step*2); else if(mid