树状数组

参考：树状数组 - OI Wiki

树状数组是一种支持 单点修改 和 区间查询 的，代码量小的数据结构。

树状数组能解决的问题是线段树能解决的问题的子集：树状数组能做的，线段树一定能做；线段树能做的，树状数组不一定可以。

lowbit

记 $x$ 二进制最低位 1 以及后面的 0 组成的数为 $lowbit(x)$。
$lowbit(x)$指的不是最低位 1 所在的位数 $k$，而是这个 1 和后面所有 0 组成的 $2^k$

计算公式

lowbit(x) = x & -x

树状数组t[i]的管辖区间

• 树状数组中，t[i]管辖的区间长度为 $2^k$，$k$ 为$lowbit(i)$.
• 所以t[i]的管辖区间为$[i-lowbit(i)+1,i]$。

区间查询

• 以维护区间和为例，查询区间$[l,r]$的区间和，可以化为区间$[1,r]$和减去区间$[1,l-1]$之和。

• 类似的，任意区间$[l,r]$的信息，都可转化成查询$[1,l-1],[1,r]$两个区间的信息再做相应操作得到。

• 查询区间$[1,x]$的过程：

  • 从 $t[x]$ 开始往前跳，有 $t[x]$ 管辖 $[x-lowbit(x)+1,x]$；
  • 令 $x \leftarrow x-lowbit(x)$，如果 $x=0$ 说明已经跳到尽头了，终止循环；否则回到第一步。
  • 将跳到的 $t[x]$ 合并。

int get(int x) // 计算a[1,2,...,x] 的区间和
{
	int ans=0;
	while(x>0) {
		ans+=t[x];
		x = x-lowbit(x);
	}
	return ans;
}

单点修改

我们的目标是快速正确地维护 $t$ 数组。为保证效率，我们只需遍历并修改管辖了 $a[x]$ 的所有 $t[j]$，因为其他的 $t$ 显然没有发生变化。

管辖$a[x]$ 的 $t[j]$ 一定包含 $t[x]$（根据性质 1），所以 $j$ 在树状数组树形态上是 $x$ 的祖先。因此我们从 $x$ 开始不断跳父亲，直到跳得超过了原数组长度为止。

设$n$ 表示 $a$ 的大小，不难写出单点修改 $a[x]$ 的过程：

• 初始令 $i \leftarrow x$。
• 修改 $c[i]$。
• 令 $i\leftarrow i+lowbit(i)$，如果 $i>n$ 说明已经跳到尽头了，终止循环；否则回到第二步。

void add(int x,int k) {
	int i=x;
	while(i<=n) {
		c[i] += k;
		i = i + lowbit(i);
	}
}

建树

一般可以直接转化为 $n$ 次单点修改，时间复杂度$\Theta(N\log N)$

例题

• P3374 【模板】树状数组 1 - 洛谷

#include <bits/stdc++.h>
// #define LL long long
#define int long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define endl '\n' 
using namespace std;
//ifstream fin("datas.in");
//ofstream fout("datas.out");
//#define fin cin
//#define fout cout
const int N = 5e5+10;

struct BIT {
    int t[N];
    int n;
    int lowbit(int x) {
        return x & -x;
    }

    void update(int i,int k) {
        int x=i;
        while(x<=n) {
            t[x]+=k;
            x+=lowbit(x);
        }
    }

    int count(int x) {
        int ans=0;
        while(x>0) {
            ans+=t[x];
            x-=lowbit(x);
        }
        return ans;
    }

    int query(int l,int r) {
        return count(r)-count(l-1);
    }
    
};

BIT bit;

signed main()
{
    IOS

    int n,m;cin>>n>>m;

    bit.n=n;

    for(int i=1;i<=n;i++) {
        int a;cin>>a;
        bit.update(i,a);
    }

    while(m--) {
        int op,x,y;cin>>op>>x>>y;
        if(op==1) {
            bit.update(x,y);
        }
        else {
            cout<<bit.query (x,y)<<endl;
        }
    }

    //fin.close(),fout.close();
    return 0;
}

区间修改，单点查询

• 例题：P3368 【模板】树状数组 2 - 洛谷

• 已知差分数组可以进行区间修改和单点查询的操作，我们可以用树状数组来维护差分数组，实现原数组的区间修改和单点查询

#include <bits/stdc++.h>
#define ll long long
#define IOS ios::sync_with_stdio(false);cin.tie(nullptr);
#define endl '\n' 
using namespace std;

const int N = 5e5+10;
int n,m;
ll c[N];

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

// 树状数组的单点修改
void add(int pos,ll x) {
    for(int i=pos;i<=n;i+=lowbit(i)) {
        c[i]+=x;
    }
}

// 差分数组实现区间修改
void add(int l,int r,ll x) {
    add(l,x),add(r+1,-x);
}

// 前缀和实现单点查询
ll query(int pos) {
    ll ans=0;
    for(int i=pos;i>0;i-=lowbit(i)) {
        ans+=c[i];
    }
    return ans;
}

signed main()
{
    IOS
    cin>>n>>m;
    ll last=0;
    for(int i=1;i<=n;i++) {
        ll a;cin>>a;
        add(i,a-last); // 构建差分数组
        last=a;
    }
    while(m--) {
        int op;cin>>op;
        if(op == 1) {
            ll x,y,k;cin>>x>>y>>k;
            add(x,y,k);  // 区间修改
        }
        else if(op==2) {
            ll x;cin>>x;
            cout<<query(x)<<endl;  // 单点查询
        }
    }

    //fin.close(),fout.close();
    return 0;
}

区间修改区间查询

• 根据上述的前缀和单点查询操作，可以得到原数组的前缀和求法如下

$$\sum_{i=1}^{p} a[i] = \sum_{i=1}^{p} \sum_{j=i}^{i} d[j]$$

$$=p\times d[1]+(p-1)\times d[2] +...+d[p] = \sum_{i=1}^{p} d[i]\times(p-i+1)$$

$$=(p+1)\sum_{i=1}^{p} d[i] - \sum_{i=1}^{p} d[i] \times i$$

• 因此可以维护两个数组的前缀和$A_1[i] = d[i]$，$A_2[i] = d[i]\times i$
• 易得$A_1[i] = d[i]+A_1[i-1]$，$A_2[i] = d[i]\times i +A_2[i-1]$
• 单点查询操作不变
• 区间查询[1,p]为

int query(int p) {
	int ans=0;
	for(int i=p;i>0;i-=lowbit(i)) {
		ans += (p+1) * A1[i] - A2[i];
	}
	return ans;
}

• 因此区间查询[l,r]为

int query(int l,int r) {
	return query(r) - query(l-1);
}

• 单点修改时要维护两个前缀和数组

void add(int p,int x) {
	for(int i=p;i<=n;i+=lowbit(i)) {
		A1[i] += x;
		A2[i] += x*p;
	}
}

• 区间修改

void add(int l,int r,int x) {
	add(l,x),add(r+1,-x);
}