问题 E: 区间求和
问题 E: 区间求和
时间限制: 1 Sec 内存限制: 128 MB
提交: 32 解决: 11
[提交][状态][讨论版][命题人:quanxing][Edit] [TestData]
题目链接: http://acm.ocrosoft.com/problem.php?cid=1690&pid=4
题目描述
给定一数列，规定有两种操作，一是修改某个元素，二是求区间的连续和。
输入
输入数据第一行包含两个正整数n,m(n<=100000,m<=500000),以下是m行，
输出
每行有三个正整数k,a,b(k=0或1, a,b<=n).k=0时表示将a处数字加上b,k=1时表示询问区间[a,b]内所有数的和。对于每个询问输出对应的答案。
样例输入
10 20
0 1 10
1 1 4
0 6 6
1 4 10
1 8 9
1 4 9
0 10 2
1 1 8
0 2 10
1 3 9
0 7 8
0 3 10
0 1 1
1 3 8
1 6 9
0 5 5
1 1 8
0 4 2
1 2 8
0 1 1 样例输出
10
6
0
6
16
6
24
14
50
41 思路：1e5的数据量，暴力区间更新查询肯定会TLE，用线段树可以快很多，此题是线段树的模板题。
代码：
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define maxn 100005
ll tree[maxn * 4];//记得开4倍空间
void pushup(int rt)
{
tree[rt] = tree[rt * 2] + tree[rt * 2 + 1];
}
void build(int l, int r, int rt)
{
if (l == r)//叶节点赋值
{
tree[rt] = 0;
return;
}
int mid = (l + r) / 2;//递归建树——左子树，右子树
build(l, mid, 2 * rt);
build(mid + 1, r, 2 * rt + 1);
tree[rt] = tree[2 * rt] + tree[2 * rt + 1];//更新父亲节点的值
}
ll qurry(int x, int y, int l, int r, int rt)
{
//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
if (x <= l && y >= r)return tree[rt];
int mid = (l + r) / 2;
ll ans = 0;
if (x <= mid)ans += qurry(x, y, l, mid, rt * 2);//如果这个区间的左儿子和目标区间有交集那么搜索左儿子
if (y > mid) ans += qurry(x, y, mid + 1, r, rt * 2 + 1);//如果这个区间的右儿子和目标区间有交集那么搜索右儿子
return ans;
}
void update(int x, int c, int l, int r, int rt)
{
if (l == r)
{
//单点更新操作
tree[rt] += c;
return;
}
int mid = (l + r) / 2;
if (x <= mid)update(x, c, l, mid, 2 * rt);
else update(x, c, mid + 1, r, 2 * rt + 1);
//维护父亲节点的总和
pushup(rt);
}
int main()
{
int n, m;
cin >> n >> m;
while (m--)
{
int k, a, b;
scanf("%d %d %d", &k, &a, &b);
if (k == 0)
{
update(a, b, 1, n, 1);
}
else
{
printf("%lld\n", qurry(a, b, 1, n, 1));
}
}
}
