树状数组

理解入门

进阶, 必看！

树状数组（Binary Indexed Tree）, 该算法多用于高效计算数列的前缀和， 区间和动态单点值的修改

这里引入一种数据结构 - 树状数组 ( Binary Indexed Tree，BIT，二分索引树 )，它只有两种基本操作，并且都是操作线性表的数据的：

  1、add( i, 1 )      (1<=i<=n)                       对第i个元素的值自增1           O(logn)
  2、sum( i )         (1<=i<=n)                       统计[1...i]元素值的和             O(logn)

试想一下，如果用HASH来实现这两个函数，那么1的复杂度是O(1)，而2的复杂度就是O(n)了，而树状数组实现的这两个函数可以让两者的复杂度都达到O(logn)

有了这两种操作，我们需要将它们转化成之前设计的数据结构的那三种操作，首先：

1. 插入(Insert)，对应的是 add(i, 1)，时间复杂度O( logn )
2. 删除(Delete), 对应的是 add(i, -1), 时间复杂度O( logn )
3. 询问(Query), 求区间和或者a[i]的值

记住i要大于1， 因为lowbit(0) = 0会死循环

基本操作

lowbit

def lowbit(self, x):
    return x & (-x)

因此i+lowbit(i)其实代表是它父级对应的index，比如c4由c3和c2累加而成，c2和c3的+lowbit(i)就是c4的位置。

i-lowbit(i)其实是没有父子祖先关系平级的最大节点，比如c4、c6、c7、a8是平级的。index=8的lowbit(8) = 8，就回到了0.

index=7的lowbit(7) = 1, 回到了c6.

更新add

更新a[i]和包含a[i]的一系列c[i]的值

//x代表位置，data带表要加上的值
void add (int x,int data)
{
    for (int i=x;i<=n;i+=lowbit(i))
            tree[i]+=data;
}

统计sum

求1到index为x的和

//求1到x的和
int sum (int x)
{
    int ans=0;
    for (int i=x;i>=1;i-=lowbit(i))
            ans+=tree[i];
    return ans;
}

树状数组创建

对每个a[i] 依次add即可， n*o(n)

实际上可以o(n)

每一个节点的值是由所有与自己直接相连的儿子的值求和得到的。因此可以倒着考虑贡献，即每次确定完儿子的值后，用自己的值更新自己的直接父亲。

// O(n)建树
void init() {
  for (int i = 1; i <= n; ++i) {
    t[i] += a[i];
    int j = i + lowbit(i);
    if (j <= n) t[j] += t[i];
  }
}

场景

有以下场景分类：

① 单点修改、区间查询 树状数组

② 区间查询、单点修改 树状数组

③ 区间查询、区间修改 树状数组

④ 二维树状数组

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

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

　　区间修改、区间查询 二维树状数组

单点修改、区间查询

原始问题

区间修改、单点查询

a[i]存的是a[i]-a[i-1]

其实这个的原理就是：通过差分把这个区间修改、单点查询的问题转化为①；

首先，假设我们要记录的数组是𝑎[1:𝑛]a[1:n]，那么我们假设有𝑑[𝑖]=𝑎[𝑖]−𝑎[𝑖−1]d[i]=a[i]−a[i−1]，且𝑑[1]=𝑎[1]d[1]=a[1]，

显然，就有𝑎[𝑖]=𝑑[1]+𝑑[2]+⋯+𝑑[𝑖]a[i]=d[1]+d[2]+⋯+d[i]，

我们在BIT中实际存储的是数组𝑑[1:𝑛]d[1:n]（准确的说是d数组的树状数组）；

先说修改：

　　我们目标是给𝑎[𝐿:𝑅]a[L:R]全部加上𝑥x，那么我们不难发现，其实𝑑[𝐿+1],𝑑[𝐿+2],⋯,𝑑[𝑅]d[L+1],d[L+2],⋯,d[R]都没有变化，

　　而变化的只有：𝑑[𝐿]d[L]增加了𝑥x，𝑑[𝑅+1]d[R+1]减少了𝑥x；

　　所以只需要add(L,x),add(R+1,-x)即可。

再说查询：

　　我们要单点查询𝑎[𝑝𝑜𝑠]a[pos]，由上可知𝑎[𝑝𝑜𝑠]=𝑑[1]+𝑑[2]+⋯+𝑑[𝑝𝑜𝑠]a[pos]=d[1]+d[2]+⋯+d[pos]，

　　那么原来的sum(pos)函数不用修改，就正好能返回𝑎[𝑝𝑜𝑠]a[pos]的值。

//BIT - 区间修改，单点查询 - st
struct _BIT{
    int N,C[MAXN];
    int lowbit(int x){return x&(-x);}
    void init(int n) //初始化共有n个点
    {
        N=n;
        for(int i=1;i<=N;i++) C[i]=0;
    }
    void add(int pos,int val)
    {
        while(pos<=N) C[pos]+=val,pos+=lowbit(pos);
    }
    void range_add(int l,int r,int x) //区间[l,r]加x
    {
        add(l,x);
        add(r+1,-x);
    }
    int ask(int pos) //查询pos点的值
    {
        int ret=0;
        while(pos>0)
        {
            ret+=C[pos];
            pos-=lowbit(pos);
        }
        return ret;
    }
}BIT;
//BIT - 区间修改，单点查询 - ed

区间查询、区间修改

我们看到，对于区间修改由于我们目标记录的是数组a[1:n]，而实际存储的是d[1:n]，d就是差分

那么已经实现了区间修改，如何完成区间查询呢？显然，区间查询的基础是快速求数组a[1:n]的前缀和，

显然数组a[1:n]的前缀和：

　　𝑎[1]+𝑎[2]+⋯+𝑎[𝑖]=𝑑[1]×𝑖+𝑑[2]×(𝑖−1)+⋯+𝑑[𝑖]×1a[1]+a[2]+⋯+a[i]=d[1]×i+d[2]×(i−1)+⋯+d[i]×1

不难发现右侧可以化成：

　　𝑑[1]×𝑖+𝑑[2]×(𝑖−1)+⋯+𝑑[𝑖]×1=[𝑑[1]×(𝑖+1)+𝑑[2]×(𝑖+1)+⋯+𝑑[𝑖]×(𝑖+1)]−[𝑑[1]×1+𝑑[2]×2+⋯+𝑑[𝑖]×𝑖]=(𝑖+1)×(𝑑[1]+𝑑[2]+⋯+𝑑[𝑖])−(𝑑[1]×1+𝑑[2]×2+⋯+𝑑[𝑖]×𝑖)d[1]×i+d[2]×(i−1)+⋯+d[i]×1=[d[1]×(i+1)+d[2]×(i+1)+⋯+d[i]×(i+1)]−[d[1]×1+d[2]×2+⋯+d[i]×i]=(i+1)×(d[1]+d[2]+⋯+d[i])−(d[1]×1+d[2]×2+⋯+d[i]×i)

这样一来，我们就可以想到，在原来的数组𝐶[𝑖]记录𝑑[𝑖]的基础上，

再搞一个数组𝐶2[𝑖]记录𝑑[𝑖]×𝑖即可。（当然，实际写代码的时候要明确，C数组和C2数组都是树状数组，不是原数组）

也就是说，使用c1=d[1:n], c2=d[1:n]*i

单点add时: c1[i]+=val, c2[i]+=val*i

区间range_add时, l,r,val: add(l,val), add(r+1,-val)

单点sum时: for(int i=pos;i>0;i-=lowbit(i)) ret+=(pos+1)*C[i]-C2[i];

区间sum,range_ask时:sum(r)-sum(l-1)

//BIT - 区间修改，区间查询 - st
struct _BIT{
    int N;
    ll C[MAXN],C2[MAXN]; //分别记录d[i]和d[i]*i
    int lowbit(int x){return x&(-x);}
    void init(int n) //初始化共有n个点
    {
        N=n;
        memset(C,0,sizeof(C));
        memset(C2,0,sizeof(C2));
    }
    void add(int pos,ll val)
    {
        for(int i=pos;i<=N;i+=lowbit(i)) C[i]+=val,C2[i]+=val*pos;
    }
    void range_add(int l,int r,ll x) //区间[l,r]加上x
    {
        add(l,x);
        add(r+1,-x);
    }
    ll ask(int pos)
    {
        ll ret=0;
        for(int i=pos;i>0;i-=lowbit(i)) ret+=(pos+1)*C[i]-C2[i];
        return ret;
    }
    ll range_ask(int l,int r) //查询区间[l,r]的和
    {
        return ask(r)-ask(l-1);
    }
}BIT;
//BIT - 区间修改，区间查询 - ed

应用

敌兵布阵问题：

题目链接

有N个军事基地，基地编号从0 到N-1，每个基地有不同数量的士兵，士兵数量可能发生增减，如何尽快的求出从第k个基地到第m个基地的士兵总数？

求逆序对数量

给一个1~n的排列，求满足i<j且a[i]>a[j]的二元组对数，比如[4,2,1,5,3]这个序列，满足条件的二元组为{<4,2>, <4,1>, <4,3>, <2,1>, <5,3>}，故逆序数是5

树状数组求逆序数的原理

首先明确树状数组在此问题中维护信息是某个区间中数字出现的个数，将源数据按其原本顺序插入树状数组，第i个数字插入的方式为将树状数组的第a[i]位设为1，同时更新覆盖到它的父区间，Query(a[i])可求得[1, a[i]]的区间和，这恰好代表第i个数字前小于等于它的个数，等于的只可能是自身，故小于它的有Query(a[i])-1个，那么大于它的显然就有i-1-(Query(a[i])-1) = i-Query(a[i])个

for (int i = 1; i <= n; i++) {
    Update(a[i], 1);
    ans += i - Query(a[i]);
}

更多题目

更多题目

只处理简单的，复杂的交给线段树。

只处理简单的，单点更新，区间查询的add,sum树。复杂的都交给线段树。

python3模板

即只能单点add，然后区间求和。

模板

# 树状数组模板
class BIT:
    def __init__(self, n):
        self.tree = [0] * n

    # 将下标 i 上的数加一
    def inc(self, i: int) -> None:
        while i < len(self.tree):
            self.tree[i] += 1
            i += i & -i

    # 返回闭区间 [1, i] 的元素和
    def sum(self, i: int) -> int:
        res = 0
        while i > 0:
            res += self.tree[i]
            i &= i - 1
        return res

    # 返回闭区间 [left, right] 的元素和
    def query(self, left: int, right: int) -> int:
        return self.sum(right) - self.sum(left - 1)

使用

class TestBIT(TestCase):
    def test_query(self):
        t = lt.BIT(100)
        t.inc(1)
        t.inc(3)
        t.inc(7)
        t.inc(50)
        assert t.sum(3) == 2
        assert t.sum(7) == 3
        assert t.query(3, 7) == 2
        assert t.query(3, 51) == 3
        t.inc(3)
        assert t.sum(3) == 3
        assert t.sum(7) == 4
        assert t.query(3, 7) == 3
        assert t.query(3, 51) == 4