周总结

桶（将数组分配到有限数量的筒子里面去，节约重复数据的空间）（与离散化处理连用，减小存储空间）

树状数组
lowbit(n)

int lowbit(int x)
{
    return x&(-x);
}

单元素加（减）法

void add(int i,int v)
{
    while(i<=n)
    {
        bit[i]+=v;
        i+=lowbit(i);
    }
}

查询前缀和

int sum(int i)
{
    long long res=0;
    while(i>0)
    {
        res+=bit[i];
        i-=lowbit(i);
    }
    return res;
}

查询区间和
sum(y)-sum(x)

二维树状数组

题：给定一个数组，分别有两个操作：给一个区间的所有数加一个值；区间求和。
典型树状数组例题，但我用了两个树状数组维护两个数据：前项和，增加的值。（注意数据范围）

#include <iostream>
using namespace std;
long long bit[2][300020];
int n,q,i,j,a,b,c;
char ch;
int v[300020];
int lowbit(int x)
{
    return x&(-x);
}
long long sum(int i,int v)
{
    long long res=0;
    while(i>0)
    {
        res+=bit[v][i];
        i-=lowbit(i);
    }
    return res;
}
void add(int i,int v, int t)
{
    while(i<=n)
    {
        bit[t][i]+=v;
        i+=lowbit(i);
    }
}
int main()
{
    cin>>n>>q;
    for(i=1; i<=n; i++)
    {
        cin>>v[i];
        add(i,v[i],0);
    }
    for(i=0; i<q; i++)
    {
        cin>>ch;
        if(ch=='C')
        {
            cin>>a>>b>>c;
            add(a,-c*(a-1),0);
            add(b+1,c*b,0);
            add(a,c,1);
            add(b+1,-c,1);
        }
        else if(ch=='Q')
        {
            cin>>a>>b;
            long long res=0;
            res += sum(b, 0) + sum(b,1) * b;
            res -=sum(a-1, 0) +sum(a-1, 1) * (a-1);
            cout<<res<<endl;
        }
    }
    return 0;
}