一. 题目

二. 理论

三. 代码

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
using namespace std;
const int N=1e5+10;
using LL=long long;

int n, m;
int a[N];

class TreeArray
{
public:
    LL tr[N];
public:
    TreeArray()
    {
        initIO();
        init();
    }

    void init()
    {
        fill(tr, tr+N, 0);
    }

    void initIO()
    {
        ios::sync_with_stdio(false);
        cin.tie(nullptr), cout.tie(nullptr);
    }

    //返回x的最后一位1
    int lowbit(int x)
    {
        return x&-x;
    }

    void add(int x, int v)
    {
        for(int i=x;i<=n;i+=lowbit(i))
            tr[i]+=v;
    }

    //得到从1~x这段的和
    LL getSum(int x)
    {
        LL sum=0;
        for(int i=x;i;i-= lowbit(i))
            sum+=tr[i];
        return sum;
    }

    //得到区间和，利用前缀和思想
    LL getLRV(int l, int r)
    {
        return getSum(r)-getSum(l-1);
    }
}ta;

int main()
{
    cin>>n>>m;
    for(int i=1;i<=n;++i)
    {
        cin>>a[i];
        ta.add(i, a[i]-a[i-1]);//处理成差分数组
    }

    while(m--)
    {
        string op;
        int l, r, x;

        cin>>op;
        if(op=="C")
        {
            cin>>l>>r>>x;
            ta.add(l, x);//差分思想
            ta.add(r+1, -x);
        }
        else if(op=="Q")
        {
            cin>>x;
            cout<<ta.getSum(x)<<endl;
        }
    }
}