秋实大哥与线段树 UESTC - 1073

墨蓝 2022-06-14 10:39 84阅读 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;
    }