【算法笔记】树状数组

前置知识：lowbit运算

想理解树状数组的原理，首先一定要理解$lowbit$运算。

模板

int lowbit(int x){ // lowbit运算，返回二进制的最低一位1
    reuturn x & -x;
}

什么叫二进制的最低一位1？

准确的说，$lowbit$返回的其实是一个数的二进制表示的最低一位1，以及它后面所有的0所构成的二进制数。

举一个例子：

比如$22$这个数，它的二进制表示是：$(10110{)}_2$，最低一位$1$也就是从右往左第一位$1$，所以$lowbit$返回的值是$(10{)}_2$，转换成十进制也就是$2$，即$lowbit(22)=2$

再比如$2232$这个数，它的二进制表示是$(100010111000{)}_2$，$lowbit$返回的也就是$(1000{)}_2$，转换成十进制也就是$8$，即$lowbit(2232)=8$

为什么模板这么写

首先要知道，计算机存储数据，都是以二进制补码的形式来存的，包含一位符号位和若干数值位，符号位为$0$表示正数，符号位为$1$表示负数，对于正数的补码，就是在正数的二进制表示前面加一个$0$，而对于负数的补码，是将负数的绝对值的二进制表示整体取反再加一后，前面再加一个$1$

举个例子，$x=2232$

$(x{)}_2=$ $(100010111000{)}_2$

$(\bar{x}{)}_2$ = $(011101000111{)}_2$

$(\bar{x}+1{)}_2$ = $(011101001000{)}_2$

所以$x$的补码等于： $0$ $100010111000$

$-x$的补码等于： $1$ $011101001000$

$x\&-x$，是不是恰好等于$1000$

这也就是$lowbit$的原理。

通过给$|x|$的二进制位取反，从而保证最低一位$1$前面的部分按位与后都为$0$。

取反后最低一位$1$的位置变为了$0$，因为他是最低一位$1$，他后面几位都是$0$，取反后都变成$1$，加一后，恰好把最低一位$1$变回了$1$。

xxxxx10000 -取反-> xxxxx01111 -加一-> xxxxx10000 -& xxxxx10000 -> 0000010000 = 10000

树状数组有什么用？

快速（$O(logn)$）进行单点修改、区间求和的操作。简单来讲，就是快速求前缀和。

为什么要用树状数组

拿一道题举例子：

有$n(1\le n\le 2\times 10^5)$个数，$q(1\le q\le 2\times 10^5)$组查询，每组查询有如下两种：

• $1$ $x$ $y$ : 将数组的第$x$个数的值加上$y$。
• $2$ $x$ $y$：求数组中第$x$个数到第$y$个数的和。

对于每个操作$2$，输出一行一个整数。

看到求区间和，第一时间能想到前缀和，但因为有操作1，这题的每个数的值随时都有可能变，也就是每次操作2的时候都要修改一遍前缀和，时间复杂度也就成了$O(q\times n)$，$2e5$的数据范围肯定是过不去的。

对这题而言，

如果用普通数组，修改操作是$O(1)$的（$a[x]=y$），但求和操作是$O(n)$的（$for(inti=x;i<=y;i++)sum+=a[i]$）

如果用前缀和数组，求和是$O(1)$的（$pre[y]-pre[x-1]$），但修改操作是$O(n)$的（$for(inti=x;i<=n;i++)pre[i]+=y$）

因为一道题分析时间复杂度指的都是最坏情况下的时间复杂度，所以这两种方法的时间复杂度都是$O(n)$

那有没有一种折中的数据结构，能让两种操作的复杂度都不高不低，来提高整体效率呢？

接下来正式来使介绍树状数组：修改和求和复杂度都是$O(logn)$的数据结构。

模板

int n;
int tr[N];

int lowbit(int x){ // lowbit运算，返回二进制的最低一位1
    return x & -x;
}

void update(int x, int c){ // 相当于a[x] += c
    for(int i = x; i <= n; i += lowbit(i)){
        tr[i] += c;
    }
}

LL getsum(int x){ // 相当于求数组中a[1 ~ x]的前缀和
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += tr[i];
    }
    return res;
}

图示

模板解释

这块看图会好理解一点。

getsum

$getsum(x)$即求从$a[1]$~$a[x]$的前缀和。

常规的前缀和，是一个数一个数的加，所以效率是$O(n)$的，那能不能将每一个从$1$~$n$的前缀和，都拆成若干个区间，并且这些区间能不重不漏的以某种特定且唯一的规律表示所有的前缀和呢？

可以基于二进制拆分的思想，每个数的二进制表示都是唯一的，每个数都是由若干$2$的整数次幂构成的。

比如$13=2^3+2^2+2^0$， $23=2^4+2^2+2^1+2^0$ ，这些二的次幂，对应着数的二进制表示的每一位$1$，也就是几个$lowbit$值。

树状数组的$getsum$的过程，便是从$x$开始，每次先查询$tr[x]$，再查询$tr[x-lowbit(x)]$, 再查询…

$tr$数组便是划分的小区间，每个区间都是$tr[x] = sum[x - lowbit(x) + 1 $ ~ $ x]$ ，区间长度为$lowbit(x)$。

比如对于$getsum(23)$，

$x=23$，$ lowbit(x) = (1)_2 = 2^0 = 1$ ，$x=x-lowbit(x)=22$ ，$tr[x]=sum[23,23]$

$x=22$，$ lowbit(x) = (10)_2 = 2^1 = 2$ ，$x=x-lowbit(x)=20$，$tr[x]=sum[21,22]$

$x=20$，$ lowbit(x) = (100)_2 = 2^2 = 4$ ，$x=x-lowbit(x)=16$，$tr[x]=sum[17,20]$

$x=16$，$ lowbit(x) = (10000)_2 = 2^4 = 16$ ，$x=x-lowbit(x)=0$，$tr[x]=sum[1,16]$

这几个$tr$加到一起，刚好是$sum[1,23]$。

因为每个区间长度为$lowbit(x)$，这几个$loewbit$加在一起还恰好等于$n$，所以一定刚好不重不漏的包含所有的数的和。

$getsum(x)$的过程，就是从$tr[x]$开始找到所有能拼凑成$x$的前缀和的区间，而每个区间的前一个区间都是$tr[x-lowbit(x)]$，所以不断地往下减$lowbit(x)$，一直到$0$，即可。

update

如果要给一个小区间的和加上$c$，对应的包含这个小区间的所有大区间的和也都要加上$c$。

观察图中的数，

$tr[3]$的父节点是$tr[4]$，$4-3=1$，$lowbit(3)=1$

$tr[6]$的父节点是$tr[8]$，$8-6=2$，$lowbit(6)=2$

$tr[12]$的父节点是$tr[16]$，$16-12=4$，$lowbit(12)=4$

…

$updatex(x)$的过程，就是从$tr[x]$开始不断地向上找父节点，而每个$tr[x]$的父节点，都是$tr[x+lowbit(x)]$，所以不断地往上加$lowbit(x)$，一直到$>n$，即可。

例题1：树状数组求前缀和

P3374 【模板】树状数组 1

const int N = 5e5 + 10;

int n, m;
int a[N];
int tr[N];

int lowbit(int x){ // lowbit运算，返回二进制的最低一位1
    return x & -x;
}

void update(int x, int c){ // 相当于a[x] += c
    for(int i = x; i <= n; i += lowbit(i)){
        tr[i] += c;
    }
}

LL getsum(int x){ // 相当于求数组中a[1 ~ x]的前缀和
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += tr[i];
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        update(i, a[i]); // 一开始树状数组都为0, 这句话即给i的位置赋值a[i] 
    }
    while(m--){
        int op, x, y;
        cin >> op >> x >> y;
        if(op == 1){
            update(x, y);
        }
        else cout << getsum(y) - getsum(x - 1) << endl; // 前y个数的和 - 前x-1个数的和 = a[x, y]的和
    }
    return 0;
}

例题2：树状数组求逆序对

用树状数组求逆序对是一个非常经典并常用的$trick$，大体原理如下：

• 从$a[1]$到$a[n]$遍历，让$a[i]$作为逆序对中的第二个数
• 对于$a[i]$，以$a[i]$作为第二个数的逆序对数即所有满足$j<i\&\&a[j]>a[i]$的$a[j]$的数量
• 简单点说，就是找$a[i]$前面比$a[i]$大的数有几个
• 可以维护一个出现次数的数组（假想是$cnt$， $cnt[x]$就表示数字$x$出现的次数），在遍历的时候，给$a[i]$加一（$cnt[a[i]]++$)
• 既然是从前往后遍历的，那是不是就能保证遍历到$a[i]$的时候，$cnt[x]$存的就是在$a[i]$前面$x$出现的次数？
• 这时候算一下$cnt$数组的前缀和，$pre[a[i]]=cnt[1]+cnt[2]+...+cnt[a[i]]$，那$pre[a[i]]$是不是就是：所有在$a[i]$前面，且小于等于$a[i]$的数的个数？$pre[N]$是不是就是：所有在$a[i]$前面，且小于等于$N$的数的个数？
• 那$pre[N]-pre[a[i]]$是不是就是：所有在$a[i]$前面，且大于$a[i]$、小于等于$N$的数的个数？如果$N$是题目中的最大值，$pre[N]-pre[a[i]]$便是你想要的数，每次累加到答案即可。
• 按上面的思路，把$cnt$数组转化成树状数组。

5910. 求逆序对

const int N = 1e5 + 10;

int n, m;
int a[N];
int tr[N];

int lowbit(int x){ // lowbit运算，返回二进制的最低一位1
    return x & -x;
}

void update(int x, int c){ // 相当于a[x] += c，这里相当于给a[x]出现次数 + c
    for(int i = x; i <= 100000; i += lowbit(i)){
        tr[i] += c;
    }
}

LL getsum(int x){ // 相当于求数组中a[1 ~ x]的前缀和，这里相当于求所有 <= x的数的出现次数
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += tr[i];
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    LL res = 0;
    for(int i = 1; i <= n; i++){
        res += getsum(100000) - getsum(a[i]); // a[i]前面，所有小于等于a[i]的数的出现次数
        update(a[i], 1); // a[i]又多了一个
    }
    cout << res << endl;
    return 0;
}

例题3：树状数组求逆序对 + 离散化

上面那道题的数据范围比较小，但一般的题都是$n\le 2\times 10^5,a[i]\le 10^9$这样的范围，如果你想像上面那样求逆序对，就要开一个$10^9$的树状数组，肯定是会超内存的，一定要离散化一下，而且不能改变数原本的相对大小（你要求逆序对，你改变他大小了还求什么）

下面讲一下怎么离散化。

离散化

常见的有两种方法，第一步都是先将所有的数都存到一个$vector$中，然后去重排序。

vector<int> v;
for(int i = 1; i <= n; i++){
    cin >> a[i];
    v.push_back(a[i]);
}
sort(v.begin(), v.end());
v.erase(unique(v.begin(), v.end()), v.end());

现在，每个$a[i]$已经从小到大的映射到了$v[0]$~$v[v.size()-1]$的位置。

接下来，就是要将$v[i]$映射到$i+1$ ，像下面这样：

这时候如果原数组是 a [ ] = { 1000000 , 1000000000 , − 1 , 0 , 100 , 1 } a[] = \{1000000, 1000000000, -1, 0, 100, 1\} a[]={1000000,1000000000,−1,0,100,1}

离散化后就是:$a^1[]=5,6,1,2,4,3$

这个时候在新的数组求逆序对，是不是效果是一样的？

离散化下面有两种方法：

用$unordered\_map$

遍历一遍直接将每个数映射到的数存起来，很好理解，直接看代码

unordered_map<int, int> ma;
for(int i = 0; i < v.size(); i++){
    ma[v[i]] = i + 1;
}

用$x$时，就改成用$ma[x]$即可。

优点：需要用数$x$时，直接用$ma[x]$就行，复杂度为$O(1)$

缺点：需要再遍历一遍数组，需要另开一个哈希表。

用lower_bound()

在$v$数组中二分查找$x$的下标，如果下标是$pos$，直接用$pos+1$即可。

int get_pos(int x){
    return lower_bound(v.begin(), v.end(), x) - v.begin() + 1;
}

用$x$时，就改成用$ge{t}_{p}os(x)$即可。

优点：不用另开数组和$map$

缺点：每次用都要二分一遍，复杂度$O(logn)$

例题

P1908 逆序对

const int N = 5e5 + 10;

int n, m;
int a[N];
int tr[N];

int lowbit(int x){ // lowbit运算，返回二进制的最低一位1
    return x & -x;
}

void update(int x, int c){ // 相当于a[x] += c
    for(int i = x; i <= m; i += lowbit(i)){
        tr[i] += c;
    }
}

LL getsum(int x){ // 相当于求数组中a[1 ~ x]的前缀和
    LL res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += tr[i];
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    vector<int> v;
    for(int i = 1; i <= n; i++){
        cin >> a[i];
        v.push_back(a[i]);
    }
    unordered_map<int, int> ma;
    sort(v.begin(), v.end());
    v.erase(unique(v.begin(), v.end()), v.end());
    m = v.size();
    for(int i = 0; i < m; i++){
        ma[v[i]] = i + 1;
    }
    LL res = 0;
    for(int i = 1; i <= n; i++){
        res += getsum(m) - getsum(ma[a[i]]);
        update(ma[a[i]], 1);
    }
    cout << res << endl;
    return 0;
}

举一反三1

https://ac.nowcoder.com/acm/contest/109459/I

const int N = 1e5 + 10;

int n, a[N], tr[N];
LL l[N];

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

LL getsum(int x){
    LL res = 0;
    for (int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

void update(int x, int c){
    for (int i = x; i < N; i += lowbit(i)) tr[i] += c;
}

void solve(){
	cin >> n;
	LL res = 0;
	memset(tr, 0, sizeof tr);
	for(int i = 1; i <= n; i++){
		cin >> a[i];
		update(a[i], 1);
		l[i] = getsum(a[i] - 1);
	}
	memset(tr, 0, sizeof tr);
	for(int i = n; i >= 1; i--){
		update(a[i], 1);
		int y = getsum(a[i] - 1);
		res += l[i] * (n - i - y) + y * (i - l[i] - 1);
	}
	cout << res << endl;
}

int main(){
	ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
	int T;
	cin >> T;
	while(T--){
		solve();
	}
	return 0;
}

举一反三2

P1637 三元上升子序列

const int N = 3e4 + 10;

int n;
int tr1[N], tr2[N];

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

void update(int tr[], int x, int d){
    for(int i = x; i <= n; i += lowbit(i)){
        tr[i] += d;
    }
}

int query(int tr[], int x){
    int res = 0;
    for(int i = x; i; i -= lowbit(i)){
        res += tr[i];
    }
    return res;
}

int main(){
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    cin >> n;
    vector<int> a(n + 1);
    for(int i = 1; i <= n; i++){
        cin >> a[i];
    }
    vector<int> b = a;
    sort(b.begin(), b.end());
    b.erase(unique(b.begin(), b.end()), b.end());
    unordered_map<int, int> ma;
    int m = b.size() - 1;
    for(int i = 1; i <= m; i++){
        ma[b[i]] = i;
    }
    vector<int> pre(n + 1, 0), suf(n + 1, 0);
    for(int i = 1; i <= n; i++){
        update(tr1, ma[a[i]], 1);
        pre[i] = query(tr1, ma[a[i]] - 1);
    }
    for(int i = n; i >= 1; i--){
        update(tr2, ma[a[i]], 1);
        suf[i] = query(tr2, m) - query(tr2, ma[a[i]]);
    }
    LL res = 0;
    for(int i = 2; i < n; i++){
        res += (LL)pre[i] * suf[i];
    }
    cout << res << endl;
    return 0;
}