Ryuji doesn't want to study （树状数组）

【传送门】：https://nanti.jisuanke.com/t/31460

【题意】给定一个数组a[N],有两种操作，

操作1，给定 l , r, 查询a[l]×L+a[l+1]×(L−1)+⋯+a[r−1]×2+a[r]的值

(L is the length of [ ll, rr ] that equals to r - l + 1r−l+1).

操作2，给定x,y，使a[x] = y

有N个数据，M种操作，对于每个操作1输出计算结果。

【题解】很容易想出来是树状数组类型的题目。但是直接计算不好计算，需要构造合适的树状数组的原数组。这个原数组并不是单纯的a[N]

考虑题目要求的序列，将其变形：

这样我们可以构造并维护两个数组的树状数组，一个是a[i]的树状数组C1[i]，一个是 a[i]*i的树状数组C2[i]。

注意这里是修改值而不是增加值，所以增加的是“新值与旧值得差”，并且要注意把原数组a[i]的值重新赋值。

【AC代码】

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1e5+;

ll a[maxn];

int n,m;

ll c1[maxn];

ll c2[maxn];

void init(){

    memset(a ,  , sizeof a);

    memset(c1 ,  , sizeof c1);

    memset(c2 ,  , sizeof c2);

}

int lowbit(int x){

    return x & (-x);

}

ll query1(int x){

    ll ans = ;

    while(x > ){

        ans += c1[x];

        x -= lowbit(x);

    }

    return ans;

}

void add1(int x , ll val){

    while(x <= n){

        c1[x] += val;

        x += lowbit(x);

    }

}

ll query2(int x){

    ll ans = ;

    while(x > ){

        ans += c2[x];

        x -= lowbit(x);

    }

    return ans;

}

void add2(int x , ll val){

    while(x <= n){

        c2[x] += val;

        x += lowbit(x);

    }

}

int main(){

    while(cin>>n>>m){

        init();

        for(int i=; i<=n; i++){

            cin>>a[i];

            add1(i , a[i]);

            add2(i , i*a[i]);

            //cout<<c1[i]<<" "<<c2[i]<<endl;

        }

        ll aa,bb,cc;

        for(int i=; i<=m; i++){

            cin>>aa>>bb>>cc;

            if(aa == ){

                cout<<(cc+)*( query1(cc) - query1(bb-) ) - (query2(cc) - query2(bb-))<<endl;

            }

            else{

                add1(bb , cc - a[bb] );

                add2(bb , bb*cc - bb*a[bb] );

                a[bb] = cc;

            }

        }

    }

    return ;

}

巴特西

Ryuji doesn't want to study （树状数组）

最新文章

热门文章