线段树练习五【线段树】

线段树练习五【线段树】"/>

线段树练习五【线段树】

>Description
一行N个方格，开始每个格子里的数都是0。现在动态地提出一些问题和修改：提问的形式是求某一个特定的子区间[a,b]中所有元素的和；修改的规则是指定某一个格子x，加上或者减去一个特定的值A。现在要求你能对每个提问作出正确的回答。1≤N≤100000,提问和修改的总数可能达到100000条。

>Input
第一行输入整数n
第二行输入整数m，表示提问和修改的总数
接下来m行表示信：M为修改，第a格加上b；C表示提问，询问(a,b)这个区间的总和

>Output
输出每次询问的结果

>Sample Input
20
6
M 1 1
M 2 2
M 3 4
M 3 -5
M 6 7
C 2 6

>Sample Output
8

>解题思路
线段树模板

修改：查找第a个数，找到以后retrun，把经过的每一个节点加上b
询问：普通查找

>代码

#include <iostream>
#include <cstdio>using namespace std;int n, m, a, b, t[400005];
char cc;void insert (int d, int l, int r) //修改：编号为d的节点，区间为l~r，查找a
{if (l == r) //区间只剩一个数了就说明找到了a{t[d] += b; //修改return;}int mid = (l + r) >> 1;if (a <= mid) insert (d * 2, l, mid);if (a > mid) insert (d * 2 + 1, mid + 1, r);t[d] += b; //修改
}
int find (int d, int l, int r, int lf, int rf) //提问：编号为d的节点，区间为l~r，查找lf~rf
{if (l == lf && r == rf) return t[d]; //查找区间与所在区间一模一样就直接返回int mid = (l + r) >> 1, sum = 0;if (lf <= mid) sum += find (d * 2, l, mid, lf, min (mid, rf));if (rf > mid) sum += find (d * 2 + 1, mid + 1, r, max (mid + 1, lf), rf); //分别查找子节点return sum;
}
int main()
{scanf ("%d%d", &n, &m);for (int i = 1; i <= m; i++){getchar();cc = getchar();scanf ("%d%d", &a, &b);if (cc == 'M') insert (1, 1, n);else if (cc == 'C') printf ("%d\n", find (1, 1, n, a, b));}return 0;
}