此页面通过工具从 csdn 导出，格式可能有问题。
题目
题目描述 Description给你N个数，有两种操作：1：给区间[a,b]的所有数增加X 2：询问区间[a,b]的数的和。 输入描述 Input Description第一行一个正整数n，接下来n行n个整数，再接下来一个正整数Q，每行表示操作的个数，如果第一个数是1，后接3个正整数，表示在区间[a,b]内每个数增加X,如果是2，表示操作2询问区间[a,b]的和是多少。输出描述 Output Description对于每个询问输出一行一个答案样例输入 Sample Input31 2 3 2 1 2 3 2 2 2 3 样例输出 Sample Output9数据范围及提示 Data Size & Hint1<=n<=2000001<=q<=200000 |
地址： http://wikioi.com/problem/1082/
思路（见代码注释）
代码
# include <cstdio>
# include <iostream>
# define N 5000000
using namespace std;
struct node{
int l,r;
long long sum,inc; // sum记录以该节点为根的树的和，inc表示该节点所统治的每个叶子节点都增加的值
};
node st[N];
int a[N];
void build(int v,int l,int r){ // 本段代码 同 数列操作1
st[v].l=l;
st[v].r=r;
if (st[v].l==st[v].r){
st[v].sum=a[l];
return ;
}
int mid = (l+r)/2;
build(v2,l,mid);
build(v2+1,mid+1,r);
st[v].sum=st[v2].sum + st[v2+1].sum;
}
void insert(int v,int l,int r,long long c){ // 插入
st[v].sum+=c*(r-l+1);
if (l==st[v].l && r==st[v].r){ // 如果正好需要这段，更新inc值，跳出
st[v].inc+=c;
return ;
}
int mid = (st[v].l+st[v].r)/2; // 向下更新
if (r<=mid) insert(v2,l,r,c);
else if (l>mid) insert(v2+1,l,r,c);
else {
insert(v2,l,mid,c);
insert(v2+1,mid+1,r,c);
}
}
long long getsum(int v,int l,int r){ // 求和
if (l==st[v].l && r==st[v].r) return st[v].sum; // 找到，返回
int mid = (st[v].l + st[v].r)/2;
if (r<=mid) return getsum(v2,l,r) + st[v].inc(r-l+1); // 如果还需要向下寻找，回溯的时候务必加上 该节点的inc值
else if (l>mid) return getsum(v2+1,l,r) + st[v].inc(r-l+1);
else return getsum(v2,l,mid) + getsum(v2+1,mid+1,r) + st[v].inc*(r-l+1);
}
int main(){
freopen(“1082.in”,“r”,stdin);
int n;
scanf("%d",&n);
for (int i(1);i<=n;i++) {
scanf("%d",&a[i]);
}
build(1,1,n);
int m,t,l,r,c;
for (scanf("%d",&m);m;m–){
scanf("%d%d%d",&t,&l,&r);
if (t & 1){
scanf("%d",&c);
insert(1,l,r,c);
}else {
//printf("%d\n",getsum(1,l,r));
cout << getsum(1,l,r) << endl;
}
}
return 0;
}
