问题 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));

         }

    }

}