这是个线段树题目，做之前必须要有些线段树基础才行不然你是很难理解的。
此题的难点就是在于你加的数要怎么加，加入你一直加到叶子节点的话，复杂度势必会很高的
具体思路
在增加时，如果要加的区间正好覆盖一个节点，则增加其节点的Inc值，不再往下走，否则要更新Sum(加上本次增量),再将增量往下传。
这样更新的复杂度就是O(log(n))在查询时，如果待查区间不是正好覆盖一个节点，就将节点的Inc往下带，然后将Inc代表的所有增量累加到Sum上后将Inc清0，接下来再往下查询。
Inc往下带的过程也是区间分解的过程，复杂度也是O(log(n))
明白思路就好写了。
下面是代码
#include <iostream> #include <cstdlib> #include <cstdio> #include <algorithm> #include <vector> #include <queue> #include <cmath> #include <stack> #include <cstring> using namespace std; #define INF 0xfffffff #define min(a,b) (a<b?a:b) #define maxn 100010 #define lson root<<1///左儿子 相当于 root*2 #define rson root<<1|1///右儿子 typedef __int64 LL; int n, m, val[maxn]; struct node { int L, R; LL Sum, Inc;///Sum保存区间的和, Inc保存这个区间内所有的数字都加上Inc int Mid() { return (L + R)/2; } } Tree[maxn*4]; void Bulid(int root,int L,int R) {/**递归建树，并且将值进行更新*/ Tree[root].L = L; Tree[root].R = R; Tree[root].Sum = Tree[root].Inc = 0; if(L == R) { Tree[root].Sum = val[L]; return ; } Bulid(lson, L, Tree[root].Mid() ); Bulid(rson, Tree[root].Mid()+1, R); Tree[root].Sum = Tree[lson].Sum + Tree[rson].Sum; } void Add(int root,int L,int R,int v) {/**更新区间内所有的值*/ if(L == Tree[root].L && R == Tree[root].R) {/**如果上述条件满足了，说明整个区间都要加上一个 v,这个时候我们只需要更新 Inc就可以了*/ Tree[root].Inc += v; return ; } /**如果这个区间并不能完全更新完，则将这个值加到Sum上*/ Tree[root].Sum += (R - L + 1)*v; /**继续向下递增*/ if( R <= Tree[root].Mid() ) Add(lson, L, R, v); else if(L > Tree[root].Mid() ) Add(rson, L, R, v); else { Add(lson, L, Tree[root].Mid(), v); Add(rson, Tree[root].Mid()+1, R, v); } } LL QuerySum(int root,int L,int R) { LL Sum = 0; /**查询操作**/ if(Tree[root].L == L && Tree[root].R == R)/**如果区间完全吻合了，可以直接算出来*/ return Tree[root].Inc * (R - L + 1) + Tree[root].Sum; /**否则我们需要向下继续更新 Inc*/ Tree[root].Sum += Tree[root].Inc * (Tree[root].R - Tree[root].L + 1); Tree[lson].Inc += Tree[root].Inc; Tree[rson].Inc += Tree[root].Inc; Tree[root].Inc = 0; /**向下递归求和*/ if(L > Tree[root].Mid() ) Sum += QuerySum(rson,L,R); else if(R <= Tree[root].Mid() ) Sum += QuerySum(lson,L,R); else { Sum += QuerySum(lson,L, Tree[root].Mid() ); Sum += QuerySum(rson,Tree[root].Mid()+1, R); } return Sum; } int main() { int Q; char ch[2]; scanf("%d %d",&n, &Q); Bulid(1,1,n); for(int i=1; i<=n; i++) scanf("%d",&val[i]); Bulid(1,1,n); while( Q-- ) { int a, b, c; scanf("%s", ch); if(ch[0] == 'Q') { scanf("%d %d",&a, &b); printf("%I64d ", QuerySum(1,a,b) ); } else { scanf("%d %d %d",&a, &b, &c); Add(1,a,b,c); } } return 0; }