//////(记得点个赞呀！)_____

题目描述

题解

给定长度为N的数列A，然后输入M行操作指令。

第一类指令形如“C l r d”，表示把数列中第l~r个数都加d。

第二类指令形如“Q X”，表示询问数列中第x个数的值。

对于每个询问，输出一个整数表示答案。

样例

10 5
1 2 3 4 5 6 7 8 9 10
Q 4
Q 1
Q 2
C 1 6 3
Q 2

算法1

本题的指令有“区间增加”和“单点查询”，而树状数组仅支持“单点查询”，需要作出一些转化来解决问题。
新建一个数组b，期初为全零。对于每条指令“C l r d”，我们把它转化成以下两条指令：
1.把b[l]加上d.
2.再把b[r+1]减去d。
执行上面两条指令后，我们再来考虑一下b数组的前缀和(b[1~x]的和)的情况：
1.对于1<=x<l，前缀和不变。
2.对于l<=x<r,前缀和增加了d。
3.对于r<x<<=N,前缀和不变(l处加d，r+1处减d，抵消)。
我们发现，b数组的前缀和b[1~x]就反映了指令“C l r d”对a[x]产生的影响。
于是，我们可以用树状数组来维护数组b的前缀（对b只有单点增加操作）。
因为各次操作之间具有可累加性，所以在树状数组上查询前缀和b[1~x]，就得到了到目前为止所有“C”指令在a[x]上增加的数值总和。再加上a[x]的初始值，就得到了“Qx”的答案。

C++ 代码

#include<bits/stdc++.h> 
using namespace std;
int n,m,a[1000000],b[1000000],c[1000000];
char o;
int js(int t)
{
    return t&(-t);
}
int jk(int x,int y)
{
    for(;x<=n;x+=js(x))
        c[x]+=y;
}
int vn(int x)
{
    int ans=a[x];
    for(;x;x-=js(x))
        ans+=c[x];
    return ans;
}
int main()
{
    scanf("%d%d",&n,&m);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for(int i=1;i<=m;i++)
    {
        scanf(" %s",&o);
        int y,z,v;
        if(o=='C')
        {
            scanf("%d%d%d",&y,&z,&v);
            jk(y,v);
            jk(z+1,-v);
        }
        else if(o=='Q')
        {
            scanf("%d",&y);
            printf("%d\n",vn(y));
        }
    }
    return 0;
}