数组计算机 Time Limit: 1000MS Memory Limit: 65536KB Problem Description
bLue 有一个神器的机器，这个机器可以读入一个数组，并按照用户要求快速地进行数组的处理和计算，它支持如下两种操作：
操作 1：把数组中第 p 个元素的值增加 v。 操作 2：计算数组中 [l, r] 区间内所有数的和。
这个机器就是这么的神奇，但是 bLue 的计算机坏掉了，你能帮他修一下吗？
Input
输入数据有多组（数据组数不超过 20），到 EOF 结束。
对于每组数据：
第 1 行输入一个整数 n (1 <= n <= 10^5)，表示数组中元素的个数。 第 2 行输入 n 个用空格隔开的整数 ai (1 <= ai <= 10^10)，表示初始输入到计算机中的数组。 第 3 行输入一个整数 q (1 <= q <= 50000)，表示用户的操作次数。 接下来 q 行，每行输入先输入 1 个整数，表示操作类型，根据不同的操作类型： 如果类型为 1，则紧接着输入 2 个用空格隔开的整数 p (1 <= p <= n) 和 v (1 <= v <= 10^10)，表示要把数组中第 p 个数的值增加 v。 如果类型为 2，则紧接着输入 2 个用空格隔开的整数 l, r (1 <= l <= r <= n)，表示要计算区间 [l, r] 内所有数的和（数组下标从 1 开始）。
Output
对于每组数据中的每次类型为 2 的操作，输出 1 行，包含一个整数，表示计算出的和。
Example Input
5 1 2 3 4 5 5 2 1 2 2 1 5 1 4 10 2 4 5 2 1 5
Example Output
3 15 19 25
代码：
#include<stdio.h> #include<string.h> #include<stdlib.h> typedef struct node { long long int data; }ST; ST tree[400000];//一般开题目要求n的四倍大小 void creat(int root, int l, int r) { int mid; if(l == r) { scanf("%lld", &tree[root].data);//不能在拆分的时候，输入数据 return ; } mid = (l + r) / 2; creat(2 * root, l, mid);//将区间不断的拆分， 左边递归调用 creat(2 * root + 1, mid + 1, r);//将区间不断的拆分， 右边递归调用 tree[root].data = tree[2 * root].data + tree[2 * root + 1].data;//递归回来求，父亲的区间值 } void updata(int p, long long int v, int l, int r, int root) { int mid; if(l == r) { tree[root].data += v; return ; } mid = (l + r) / 2; if(p <= mid) updata(p, v, l, mid, 2 * root);//判断p是在左边的区间还是右边的区间 else updata(p, v, mid+1, r, 2 * root + 1); tree[root].data = tree[2 * root].data + tree[2 * root + 1].data;//递归回来，更新父亲的区间值 } long long sum(int L, int R, int l, int r, int root) { int mid; long long int red = 0; if(L <= l && R >= r) return tree[root].data;//如果区间满足L,R的范围就返回对于的区间值 mid = (l + r) / 2; if(L <= mid) red += sum(L, R, l, mid, 2 * root);//左边求值 同时求和 if(R > mid) red += sum(L, R, mid + 1, r, 2 * root + 1);//右边求值 同时求和 return red;//返回结果 } int main() { int n, m, num, p, L, R; long long int v; while(~scanf("%d", &n)) { creat(1, 1, n);//从下标1到n构建 线段树 数组， 分别表示 根节点下标，区间左边界，区间右边界 scanf("%d", &m);//m次操作 while(m--) { scanf("%d", &num); if(num == 1)//第p个数的值增加v { scanf("%d %lld", &p, &v); updata(p, v, 1, n, 1);//更新值，同时调整线段树 } else if(num == 2)//求L,R区间的值 { scanf("%d %d", &L, &R); printf("%lld\n", sum(L, R, 1, n, 1));//求值 } } } return 0; }