树状数组 | wjyppm's Blog

1.概念与代码

1.0导入

树状数组是一种支持单点修改和区间查询的，代码量小的数据结构。利用数的二进制特性进行检索的一种树状的结构

显然可得树状数组是多叉树

如图，我们对 $t[7]$ 进行检索

查询的过程就是每次去掉最后的二进制位的1，例如我们对7进行前缀和求值。sum(7)=t[7]+t[6]+t[4]

7的二进制是111 去掉最后的1，得110 即6
去掉6的二进制最后一个1，即100，即4
显然4不能再去1了，再去1就是0了

接下来进行维护（加），维护的过程就是每次在二进制的最后的1再加1.例如更新了 $a_3$ 就要修改 $t[3]$ ， $t[4]$ ， $t[8]$

3的二进制是11，在最后的1加上1就是100 即4，更新
4的二进制是100，在最后的1加上1就是1000，即8，更新
8的二进制再加就超范围了，这时停止

显然这里有一个关键问题，如何找到二进制1，就是lowbit

1.1 lowbit

这里先给出代码

1
2
3

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

功能就是找到二进制下最后一个1，自行证明一下。

1.2 代码

P3374 单点修改区间查询（原汁原味）

#include<iostream>
using namespace std;
const int MN=5e5+15;
int lowbit(int x){
    return x & -x;
}
int t[MN],n,m;
void add(int x,int k){
    while (x<=n)//防止超出边界
    {
        //加值让后加上末尾的1
        t[x]+=k;
        x+=lowbit(x);
    }
}
int sum(int x){
    int ans=0;
    while (x>0)
    {
        //加值让后减去末尾的1
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(int i=1;i<=n;i++){
        int t;
        cin>>t;
        add(i,t);
    }
    for(int i=1;i<=m;i++){
        int x,y,op;
        cin>>op>>x>>y;
        if(op==1){
            add(x,y);
        }else{//区间查询，sum代表1~k的前缀和
            cout<<sum(y)-sum(x-1)<<endl;
        }
    }
}

0为下表的树状数组，感谢牢学长（@Renamoe）

0-index

2.应用

1.区间修改+单点查询

HDU-1556

N个气球排成一排，从左到右依次编号为1,2,3…N.每次给定2个整数 $a$ , $b$ ( $a <= b$ ),lele便为骑上他的“小飞鸽"牌电动车从气球a开始到气球b依次给每个气球涂一次颜色。但是 $N$ 次以后lele已经忘记了第 $I$ 个气球已经涂过几次颜色了，你能帮他算出每个气球被涂过几次颜色吗？
Input
每个测试实例第一行为一个整数 $N,(N <= 100000)$ .接下来的N行，每行包括2个整数 $a$ , $b$ $(1 <= a <= b <= N)$ 。
当 $N = 0$ ，输入结束。

Output

每个测试实例输出一行，包括 $N$ 个整数，第 $I$ 个数代表第 $I$ 个气球总共被涂色的次数。

1 2	1 1 1 3 2 1

定义 $a[i]$ 为气球涂色的次数，若用暴力法求解显然复杂度是 $O(n^2)$ 过不去。我们用上面提到的，单点修改区间查询，显然修改是 $O(n)$ 的，那么反而更差，最终即为 $O(n^2log_2n)$ ，难受

对于一段区间重复操作，我们考虑差分。差分是一个很神奇的东西，能将区间问题转换为端点问题。自己先看看定义吧（~~其实是我懒~~）

代码如下

#include<iostream>
#include<cstring>
using namespace std;
const int MN=1e5+15;
int t[MN],n;
int lowbit(int x){
    return x & -x;
}
void add(int x,int k){
    while (x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
int ask(int x){
    int ans=0;
    while (x>0)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    while (1)
    {
        memset(t,0,sizeof(t));
        cin>>n;
        if(!n) break;
        for(int i=1;i<=n;i++){
            int a,b;//a->L b->R
            cin>>a>>b;
            add(a,1);
            add(b+1,-1);
        }
        for(int i=1;i<=n;i++){
            cout<<ask(i)<<" ";
        }
        cout<<endl;
    }
    
    return 0;
}

显然两个for循环时间复杂度均为 $O(nlog_2n)$ 可以啦

（~~不是哥们为啥这个差分题非要用树状数组+差分做啊~~）

2.区间修改+区间查询

老生常谈线段树

已知一个数列，你需要进行下面两种操作：

将某区间每一个数加上 $k$ 。
求出某区间每一个数的和。

第一行包含两个整数 $n, m$ ，分别表示该数列数字的个数和操作的总个数。

第二行包含 $n$ 个用空格分隔的整数，其中第 $i$ 个数字表示数列第 $i$ 项的初始值。

接下来 $m$ 行每行包含 $3$ 或 $4$ 个整数，表示一个操作，具体如下：

1 x y k：将区间 $[x, y]$ 内每个数加上 $k$ 。
2 x y：输出区间 $[x, y]$ 内每个数的和。

输入

输出

1
2
3

11
8
20

对于 $30\%$ 的数据： $n \le 8$ ， $m \le 10$ 。
对于 $70\%$ 的数据： $n \le {10}^3$ ， $m \le {10}^4$ 。
对于 $100\%$ 的数据： $1 \le n, m \le {10}^5$ 。

保证任意时刻数列中所有元素的绝对值之和 $\le {10}^{18}$ 。

这里我们需要进一步强化对于差分的理解，你已经理解了差分是干嘛的，接下来差分我们显然可得两个性质

$a_i$ 的值是 $b_i$ 的前缀和，即 $a_n=\sum_{i=1}^nb_i$
计算 $a_k$ 的前缀和 $sum=\sum_{i=1}^ka_i=\sum_{i=1}^k\sum_{j=1}^ib_i=\sum_{i=1}^k(n-i+1)b_i$

ok这里直接放推导过程

$a_1+a_2+a_3+...+a_k$

由性质2可得

$=kB_1+(k-1)B_2+(k-2)B_3+...+(k-(k-1))B_k$

$=k(B_1+B_2+B_3+...+B_k)-(B_2-2B_3-...-(k-1)B_k)$

$=k\sum_{i=1}^kB_i-\sum_{i=1}^k(i-1)B_i$

显然我们可以用2个树状数组来维护前缀和

代码如下

#include<iostream>
#define ll long long
using namespace std;
ll lowbit(ll x){
    return x & -x;
}
const int MN=1e5+15;
ll t1[MN],t2[MN],m,n,a[MN];
void add(ll *t,ll x,ll k){
    while (x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
ll ask(ll *t,ll x){
    ll ans=0;
    while (x>0)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
int main(){
    cin>>n>>m;
    for(ll i=1,pre=0;i<=n;i++){
        ll t;
        cin>>t;
        //差分数组定义
        add(t1,i,t-pre);
        add(t2,i,(i-1)*(t-pre));
        pre=t;
    }
    while (m--)
    {
        ll q,l,r,k;
        cin>>q>>l>>r;
        if(q==1){
            cin>>k;
            add(t1,l,k);
            add(t1,r+1,-k);
            add(t2,l,k*(l-1));
            add(t2,r+1,-k*r);//-k*r=-k*(r+1-1)
        }else{
            cout<<r*ask(t1,r)-(l-1)*ask(t1,l-1)-ask(t2,r)+ask(t2,l-1)<<endl;//这里把括号去掉了
        }
    }
    
    return 0;
}

3.偏序问题（逆序对+离散化）

其实偏序问题应当用CDQ分治去做的，但是对于一维的来说，树状数组显然复杂度更优（ $O(n\sqrt n)$ < $O(nlog_2n)$ ）

P1908

对于给定的一段正整数序列，逆序对就是序列中 $a_i>a_j$ 且 $i<j$ 的有序对。
算出给定的一段正整数序列中逆序对的数目。注意序列中可能有重复数字。

用这个解逆序对问题用到一个技巧，即对值域建树状数组

这样就很好处理了，每处理一个数字，树状数组下表所对应的元素数值加一，统计前缀和，就是逆序对的数量

这里倒序处理，注意离散化

#include<iostream>
#include<algorithm>
using namespace std;
const int MN=5e5+15;
struct node
{
    int v,id;
};

int n,t[MN],rnk[MN];
node a[MN];
int lowbit(int x){
    return x & -x;
}
int ask(int x){
    int ans=0;
    while (x>0)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
void add(int x,int k){
    while (x<=n)
    {
        t[x]+=k;
        x+=lowbit(x);
    }
}
bool cmp(node x,node y){
    if(x.v==y.v){
        return x.id<y.id;
    }
    return x.v<y.v;
}
int main(){
    cin>>n;
    for(int i=1;i<=n;i++){
        cin>>a[i].v;
        a[i].id=i;
    }
    sort(a+1,a+1+n,cmp);
    for(int i=1;i<=n;i++){
        rnk[a[i].id]=i;
    }
    long long ans=0;
    for(int i=n;i>0;i--){
        add(rnk[i],1);
        ans+=ask(rnk[i]-1);
    }
    cout<<ans;
    return 0;
}