题解：AT_abc442_d [ABC442D] Swap and Range Sum

题目传送门。

思路

这一道题一看又有修改又有求和，普通的做法肯定过不了，这时我们就要请出可以修改和求和的工具，线段树和树状数组。由于作者比较懒，所以就只写出了树状数组的写法。

AC CODE

#include<bits/stdc++.h>
using namespace std;
int n,m;
int a[200005],c[200005];
int lowbit(int x){return x&(-x);}
void add(int x,int y){//修改函数。
    for(int i=x;i<=n;i+=lowbit(i)){
        c[i]+=y;
    }
}
int sum(int x){//求和函数。
    int cnt=0;
    for(int i=x;i>=1;i-=lowbit(i))cnt+=c[i];
    return cnt;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        cin>>a[i];
        add(i,a[i]);//将每个a_i进行求和。
    }
    while(m--){
        int op;
        cin>>op;
        if(op==1){
            int x;
            cin>>x;
            int t=sum(x+1)-2*sum(x)+sum(x-1);//求出两数的差。
            add(x,t);
            add(x+1,-t);//进行修改。
        }
        else{
            int l,r;
            cin>>l>>r;
            cout<<sum(r)-sum(l-1)<<'\n';//求和查询
        }
    }
    return 0;
}

管理大大求过。