1
一、一维树状数组
1、单点修改+区间查询（应用：求逆序对，求区间最大值）
lowbit()函数：求x的补码（x&-x）
意义:得到的是x的二进制表示中，最低位的1表示的数
如 5 二进制表示为101，所以最低位的1所在的位置是0，所以lowbit(5)=2^0=1;
后缀数组：
sum[1]=a[1];
sum[2]=a[2]+a[1];
sum[3]=a[3];
sum[4]=a[4]+a[3]+a[2]+a[1];
sum[5]=a[5];
即对于后缀和sum[x]，表示的是从a[x]开始向前共加lowbit(x)项。
当我们修改某一点a[x]的值时，要将修改的信息向上传递，而且通过加上lowbit(x)可以发现对应的sum中恰好含有a[x]这一项，这样就可以对所有含有a[x]的sum进行修改。
查询区间1~x的和时，通过lowbit可以把大的区间划分成各个不重叠的小区间，然后加起来即可。（把后缀数组写出来就可以发现规律）
代码：

单点修改：

void update(int p,int C)
{
    int i=p;
    while(i<=n)
    {
        sum[i]+=C;
        i+=(i&(-i));
    }
}

区间查询：

int query(int x)
{
    int ans=0;
    while(x>=1)
    {
    	ans+=sum[x];
    	x-=(x&-x);
    }
    return ans;
}

求逆序对
求最大值：

2、区间修改+单点查询
利用差分序列的思想，此时树状数组的意义与前面不同。
对于数组a[i],记此时tree[i]=a[i]-a[i-1];（a[0]=0）tree[1]=a[1];
有 a[i]=tree[1]+……+tree[i];
所以当要修改区间（l~r）,使每个数都加上c时，只需要令tree[l]+=c,令tree[r+1]-=c;（即使得区间
l~r内的数与前面的数的差值增大，与后面的差值减小），即转化为对单点的修改，对单点修改可以通过树状数组来实现，再通过求树状数组前x项和就可以得到a[x]的值。
单点修改：

void update(int p,int c)
{
    while(p<=n)
    {
        tree[p]+=c;
        p+=(p&-p);
    }
}

区间修改：

void range_update(int l,int r,int c)
{
    update(l,c);
    update(r+1,-c);
}

区间查询：

int query(int p)
{
    int sum=0;
    while(p>=1)
    {
        sum+=tree[p];
        p-=(p&-p);
    }
    return sum;
}

3、区间修改+区间查询
同样是基于2中的差分思想。对于2中的差分序列，
当要求前1项和时，用一次tree[1];
求前两项和时，用二次tree[1],一次tree[2];
以此类推；
当求前p项和时，用p次tree[1],（p-1）次tree[2],……，（p-i+1）次tree[i],所以前p项和为
ans=(p+1) 乘（tree[i]的前p项和）-（i * tree[i]的前p项和）；
因此，我们可以通过维护两个数组来解决；
tree1[i]=tree[i];
tree2[i]=i*tree[i];
因此要求前p项和时，只需要进行一次查询即可，求区间（l~r）时，进行两次查询，然后相减即可。
进行修改时，对于tree1[i],与 2 中一样修改。对于tree2[i],在前面的基础上乘个i即可。同样转化为单点修改问题。

单点修改：

void update(int p,int c)
{
    while(p<=n)
    {
        tree1[p]+=c;
        tree2[p]+=c*p;
        p+=(p&-p);
    }
}

区间修改：

void range_update(int l,int r,int c)//区间修改
{
    update(l,c);
    update(r+1,-c);
}

前p项和查询：

int query(int p)//求前p项和
{
    int sum=0;
    int i=p;//p要固定不变
    while(i)
    {
        sum+=(p+1)*tree1[i]-tree2[i];
        i-=(i&-i);
    }
    return sum;
}

区间查询：

int query(int l,int r)//区间查询
{
    return query(r)-query(l-1);
}

二、二维树状数组
1、单点修改+区间查询

2、区间修改+单点查询

3、区间修改+区间查询