2011-06-28 16:38:02Morris
d799. 区间求和 (樹狀數組版本)
d799. 区间求和
內容 ：
在本题描述之前，首先衷心感谢morris1028为线段树的高级数据结构算法打开了大门！
给你N个数据，不断地改变这N个数据的同时也不停地问你某个区间中所有元素的和！
輸入說明
：
只有一笔测试数据。
第一行是N(0<N<=500000)，接下来有N个数a[i][j](0<=a[i,j]<=32767)。
然后是一个数字Q(0<Q<=500000)，接下来有Q组要求和询问。
每组要求或询问的格式是：首先是一个数 v (v=1或2)，
若v=1则表示是要求，接下来有三个数据 x y k (0<x<=y<=N且0<=k<=1000)，表示从第x个数据至第y个数据每个都加上k；
若v=2则表示是询问，接下来有两个数据 x y (0<x<=y<=N)，你得输出从第x个数据至第y个数据的所有元素的和。
輸出說明
：
如果是要求，则不用输出；
如果是询问，则输出所要求的元素之和。
範例輸入 ：
4 1 2 3 4 5 2 1 3 1 1 3 1 2 1 3 1 1 4 1 2 1 4
範例輸出 ：
6 9 17
提示
：
32767×500000>2147483647
出處
：
/**********************************************************************************/
/* Problem: d799 "区间求和" from 线段树 */
/* Language: C */
/* Result: AC (1192ms, 15896KB) on ZeroJudge */
/* Author: morris1028 at 2011-06-28 15:57:26 */
/**********************************************************************************/
#include<stdio.h>
#define N 500001
long long sum[N];
long long c1[N], c2[N];
int A[N], lowbit[N], n;
int Input() {
char cha;
unsigned int x = 0;
while(cha = getchar())
if(cha != ' ' && cha != '\n') break;
x = cha-48;
while(cha = getchar()) {
if(cha == ' ' || cha == '\n') break;
x = x*10 + cha-48;
}
return x;
}
long long query(long long C[], int i) {
long long sum = 0;
while(i > 0) {
sum += C[i];
i -= lowbit[i];
}
return sum;
}
void update(long long C[], int i, long long k) {
while(i <= n) {
C[i] += k;
i += lowbit[i];
}
}
main() {
int a, q, i, j, k;
long long Ans;
char v;
for(a = 1; a < N; a++)
lowbit[a] = a & (-a);
scanf("%d", &n);
for(a = 1; a <= n; a++)
A[a] = Input();
for(a = 1; a <= n; a++)
sum[a] = sum[a-1] + A[a];
scanf("%d", &q);
getchar();
while(q--) {
v = getchar();
if(v == '1') {
i = Input(), j = Input(), k = Input();
update(c1, i, k);
update(c1, j+1, -k);
update(c2, i, k*i);
update(c2, j+1, -k*(j+1));
}
else {
i = Input(), j = Input();
Ans = sum[j] - sum[i-1];
Ans += (j+1)*query(c1, j) - query(c2, j);
Ans -= i*query(c1, i-1) - query(c2, i-1);
printf("%lld\n", Ans);
}
}
return 0;
}
上一篇：a164. 區間最大連續和