第五十六章 树状数组（一）

一、前缀和的缺陷

我们在很久之前介绍过前缀和算法。

我们先来分析一下前缀和算法的优点和缺陷。

这个算法的优点在于能够在$O(1)$的时间复杂度内算出某段区间的和。但是，这个过程的前提是我们没有去修改原数组。也就是说，如果我们在后续过程中修改了原数组中的某个数，我们就必须去修改前缀和数组。

假设我们修改的是原数组中的第一个元素。由于原数组的前$n$项和必定包括第一个元素，所以我们前缀和数组中的每一个元素都需要重新修改。那么这个过程的时间复杂度是$O(n)$的。此时这个前缀和数组相当于没有发挥作用。

总结一下，当我们边修改数组中的某元素边求前缀和的时候，我们原本的前缀和算法就会退化成$O(n)$。

二、树状数组

1、作用

当我们遇到原数组内的元素需要一边修改一边求区间和的时候，就需要用到树状数组。

对于树状数组而言，当修改一个原数组中的元素，我们修改前缀和数组的时候，此时的时间复杂度是$O(logn)$。当我们查询某段区间和的时候，时间复杂度也是$O(logn)$。

与前缀和算法相比，查询操作从$O(1)$到了$O(logn)$，修改到操作从$O(n)$到了$O(logn)$。

2、算法分析

这个算法解释起来相当麻烦，所以作者这里推荐一个讲解树状数组的视频：

B站：〔manim | 算法 | 数据结构〕 完全理解并深入应用树状数组 | 支持多种动态维护区间操作

3、算法实现

看过上面B站视频的讲解后，我们发现树状数组重要的有三个函数，一个函数是：lowbits()，一个函数是插入，一个函数是查询。

（1）lowbits()

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

（2）插入

void add(int pos, int x)
{for(int i = pos; i <= n; i += lowbits(i))tree[i] += x;return;
}

（3）查询

int quary(int pos)
{int res = 0;for(int i = pos; i; i -= lowbits(i))res += tree[i];return res;
}

三、例题

P3374 【模板】树状数组 1

1、问题

题目描述

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

• 将某一个数加上 $x$

• 求出某区间每一个数的和

输入格式

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

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

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

• 1 x k 含义：将第 $x$ 个数加上 $k$

• 2 x y 含义：输出区间 $[x,y]$ 内每个数的和

输出格式

输出包含若干行整数，即为所有操作 $2$ 的结果。

样例 #1

样例输入 #1

5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4

样例输出 #1

14
16

提示

【数据范围】

对于 $30\%$ 的数据，$1\le n\le 8$，$1\le m\le 10$；
对于 $70\%$ 的数据，$1\le n,m\le 10^4$；
对于 $100\%$ 的数据，$1\le n,m\le 5\times 10^5$。

数据保证对于任意时刻，$a$ 的任意子区间（包括长度为 $1$ 和 $n$ 的子区间）和均在 $[-2^{31},2^{31})$ 范围内。

样例说明：

故输出结果14、16

2、代码

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N = 5e5 + 10;
int a[N];
ll tree[N];
int n, m;int lowbits(int x)
{return x & -x;
}void add(int pos, int x)
{for(int i = pos; i <= n; i += lowbits(i))tree[i] += x;return;
}ll quary(int pos)
{ll res = 0;for(int i = pos; i; i -= lowbits(i))res += tree[i];return res;
}void solve()
{cin >> n >> m;for(int i = 1; i <= n; i ++ )cin >> a[i];for(int i = 1; i <= n; i ++ )add(i, a[i]);while(m -- ){int op;cin >> op;if(op == 1){int pos ,x;cin >> pos >> x;add(pos, x);}else{int l ,r;cin >> l >> r;cout << quary(r) - quary(l - 1) << endl;}}
}int main()
{ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);solve();
}