一开始超时，然后优化了好久。。
开始给的n个值就算是初始值吧。我在建树的时候就把每个结点的和都算好了，存在info里，其实先建树再一个一个插入也是可以的。后面的操作中要增加的值就是附加值，我把它存在add里 。
关键的优化就是，如果一个附加值正好加在线段树里的一个结点所代表的那个区间上，就不用再往子区间加下去了，加在那个结点就行。然后在查询的时候如果碰到了有附加值的结点又要往子区间去查询，就顺便把那个点的附加值传给子区间 。
这样就少了很多操作，不然在极端一些的情况下，加一个数要操作到线段树中的每一个结点，操作数就是O（n）了。
Source Code
| Problem: 3468 |
User: yueashuxia |
|
| Memory: 7188K | Time: 1563MS | |
| Language: C++ | Result: Accepted |
- Source Code
#include <stdio.h>
#include <string.h>
#include <iostream>
#include <algorithm>
using namespace std;
#define size 100001
struct xds
{
int a, b ;
int lson, rson ;
long long info, add ;//info存储区间和，add存储该区间每个增加的数
}tree[size*3] ;
int tot ;
long long num[size+1] ;
void make_xds(int s, int t)
{
int now = ++tot ;
tree[now].a = s ;
tree[now].b = t ;
tree[now].add = 0 ;
if(t - s > 0)
{
int mid = (s + t) >> 1 ;
tree[now].lson = tot + 1 ;
make_xds(s, mid) ;
tree[now].rson = tot + 1 ;
make_xds(mid + 1, t) ;
tree[now].info = tree[tree[now].lson].info + tree[tree[now].rson].info ; //建树时把和存好
}
else { //子结点
tree[now].lson = tree[now].rson = 0 ;
tree[now].info = num[s] ;
}
}
void update(int p, int s, int t, int info)
{
if(tree[p].a == s && tree[p].b == t)//正好加在这个节点就直接返回
{
tree[p].add += info ;
return ;
}
tree[p].info += info * (t - s + 1) ; //s和t一定在p结点的区间内
if(tree[p].a == tree[p].b) return ;
int mid = (tree[p].a + tree[p].b) >> 1 ; //往下传递
if(s > mid) update(tree[p].rson, s, t, info) ;
else if(t <= mid) update(tree[p].lson, s, t, info) ;
else update(tree[p].lson, s, mid, info), update(tree[p].rson, mid + 1, t, info) ;
}
long long query(int p, int s, int t)
{
if(tree[p].a == s && tree[p].b == t) {
return tree[p].info + tree[p].add * (tree[p].b - tree[p].a + 1);
}
if(tree[p].add) // 把add值往左右子树传递
{
tree[p].info += (tree[p].b - tree[p].a + 1) * tree[p].add ;
tree[tree[p].lson].add += tree[p].add ;
tree[tree[p].rson].add += tree[p].add ;
tree[p].add = 0 ;
}
int mid = (tree[p].a + tree[p].b) >> 1 ;
if(t <= mid) return query(tree[p].lson, s, t) ;
else if(s > mid) return query(tree[p].rson, s, t) ;
else return query(tree[p].lson, s, mid) + query(tree[p].rson, mid + 1, t) ;
}
int main (){
int Q, i, j, N ;
long long k ;
char ord[2] ;
scanf("%d%d", &N, &Q) ;
tot = 0 ;
for (i = 1; i <= N; i ++)
{
scanf("%lld", &num[i]);//先存好
}
make_xds(1, N) ; //再建树
while(Q --)
{
scanf("%s%d%d", ord, &i, &j);
switch (ord[0])
{
case 'Q': printf("%lld/n", query(1, i, j)); break ;
case 'C': scanf("%lld", &k);update(1, i, j, k) ;
}
}
//system ("pause") ;
return 0 ;
}