秋实大哥与线段树 UESTC

秋实大哥与线段树 UESTC - 1073

墨蓝 2022-06-14 10:39 196阅读 0赞

秋实大哥与线段树 UESTC - 1073

Problem

“学习本无底，前进莫徬徨。” 秋实大哥对一旁玩手机的学弟说道。

秋实大哥是一个爱学习的人，今天他刚刚学习了线段树这个数据结构。

为了检验自己的掌握程度，秋实大哥给自己出了一个题，同时邀请大家一起来作。

秋实大哥的题目要求你维护一个序列，支持两种操作：一种是修改某一个元素的值；一种是询问一段区间的和。

Input

第一行包含一个整数nn，表示序列的长度。

接下来一行包含nn个整数aiai，表示序列初始的元素。

接下来一行包含一个整数mm，表示操作数。

接下来mm行，每行是以下两种操作之一：

1 x v : 表示将第x个元素的值改为v
2 l r : 表示询问[l,r]这个区间的元素和
1≤n，m，v，ai≤1000001≤n，m，v，ai≤100000，1≤l≤r≤n1≤l≤r≤n。

Output

对于每一个22 ll rr操作，输出一个整数占一行，表示对应的答案。

Sample Input

3
1 2 3
3
2 1 2
1 1 5
2 1 2

Sample Output

3
7

ps：线段树

代码如下：

#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long ll;
const int  maxn = 100000+100;
ll a[maxn];
int n, m;
inline ll lowbit(int x) {
    return x&(-x);
}
inline void updata(int x, int p) {
    while(x <= n) {
        a[x] += p;
        x += lowbit(x);
    }
}
inline ll sum(int x) {
    ll res = 0;
    while(x) {
        res += a[x];
        x -= lowbit(x);
    }
    return res;
}
int main() {
    scanf("%d", &n);
    for(int i = 1; i <= n; i++) {
        ll x;
        scanf("%lld", &x);
        updata(i, x);
    }
    scanf("%d", &m);
    for(int i = 0; i < m; i++) {
        ll b, x, y;
        scanf("%lld %lld %lld", &b, &x, &y);
        if(b == 1){
            ll p = sum(x) - sum(x-1);
            updata(x, -p);
            updata(x, y);
        }
        else {
            printf("%lld\n",sum(y) - sum(x-1));
        }
    }
    return 0;
}