线段树练习五【线段树】"/>
线段树练习五【线段树】
>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;
}
更多推荐
线段树练习五【线段树】
发布评论