企业官网建设流程全解析

呵呵呵呵呵呵呵呵呵呵

Today我们要讲树状数组。

先从问题引入主题：

(其中，100%的数据保证 “1 ≤ n, m ≤ 500,000”)

乍一眼看上去使用前缀和做的，先写一下暴力代码。

#include <bits/stdc++.h> // 万恶之源inf + 1(== inf) using namespace std; // 万恶之源inf + 2(== inf) int n, m; // n个数字, m次询问 int a[500005]; // a数组 int s[500005]; // 前缀和数组 int main() { cin >> n >> m; for (int i = 1; i <= n; i++) { // 输入n个数 cin >> a[i]; s[i] = s[i - 1] + a[i]; // 前缀和初始化 } while (m--) { int op, x, y; // 如果op是1, 那么a[x] += y, 否则输出a[x] ~ a[y]的数值之和 cin >> op >> x >> y; if (op == 1) { for (int i = x; i <= n; i++) s[i] += y; // 如果一个点变了, 那么后面所有前缀和数组的值都会变 } else { cout << s[y] - s[x - 1] << '\n'; // 输出a[x] ~ a[y]的和 } } } // 完结, 不撒花(T_T) // 因为这个代码是错误的

为什么是错误的呢？

来看一下时间复杂度：最坏x=1，循环1~n，又有m次，时间复杂度就是O(nm)。

前缀和慢就慢在这个增加上面，因此，我们今天的重头戏上场了——

什么是树状数组

• 核心用处：高效单点修改 + 区间前缀和查询，时间复杂度是 O(logn)。
• 优点：代码极短、常数小，时间快。
• 缺点：扩展性弱，只能解决这类问题。

树状数组实现

相比于普通的数组前缀和，树状数组管辖的区域相对小一点。

管辖区域特定要求：

管辖区应为最后一个出现的1代表的十进制数。

如 6 -> 110 管辖(10)的十进制数，也就是2个数，范围是5~6；

再如 16 -> 10000 管辖(10000)的十进制数，也就是16个数，范围是1~16；

不同的数有着不同的管辖范围。

那该如何解决呢？

令下标为x，val为x & -x，则c[x]的管辖区域为[x - val ~ x]。

那为什么不是别的，偏偏是x & -x？

let us remind what is 二进制吧：

计算机运算是利用补码实现的。

来计算16&-16：

00000000 00000000 00000000 00010000

&

11111111 11111111 11111111 11110000

↓

00000000 00000000 00000000 00010000

||

既然要完成单点加&求区间和，树状数组都可解决，时间复杂度是,且x常数很小。

代码稍微处理一下即可：

#include <bits/stdc++.h> // 万恶之源 inf + 3(== inf) using namespace std; // 万恶之源 inf + 4(== inf) int n, m; int a[500005], c[500005]; // a原数组，c树状数组 // 单点加：a[x] += y void add(int x, int y) { // 既然加了一个点，那么所有的管辖区都要变 while (x <= n) { c[x] += y; x += x & -x; // lowbit(x) = x & -x, 因为c++运算都是按补码完成的 } } // 查询前缀和：1~x 的和 int query(int x) { int ans = 0; while (x > 0) { ans += c[x]; // 求出x所有管辖区域的c[x]之和 x -= x & -x; } return ans; } int main(){ cin >> n >> m; for (int i = 1; i <= n; i++) { cin >> a[i]; add(i, a[i]); // 初始化树状数组 } while (m--) { int op, x, y; cin >> op >> x >> y; if (op == 1) { add(x, y); // 操作1：a[x] += y } else { cout << query(y) - query(x - 1) << '\n'; // 操作2：查询[x,y]和 } } } // 完结，撒花~ // *★,°*:.☆(￣▽￣)/$:*.°★* 。