《树状数组》
-
解决的问题：
-
维护一个长度为
n的数组arr（初始通常全为0）。 -
支持操作：
-
单点更新（Update）：将
arr[i]的值增加（或修改为）delta（或value）。 -
前缀查询（Query）：快速查询
arr[1] + arr[2] + ... + arr[i]的和（前缀和）。
-
-
衍生操作：
-
区间查询（Range Query）：利用前缀和相减（
Query(r) - Query(l-1)）计算arr[l] + ... + arr[r]的和。 -
单点查询（Point Query）：结合差分思想（构建差分数组的树状数组）或直接用
Query(i) - Query(i-1)（如果支持单点查询）。 -
区间更新（Range Update）：结合差分思想（构建差分数组的树状数组），支持
arr[l..r]每个元素增加delta。 -
求逆序对（Inversion Count）：离散化 + 树状数组统计。
-
-
-
应用场景总结
-
动态单点修改 + 区间和查询： 最直接的应用。
-
动态逆序对计数： 离散化原始数据，然后从左到右（或从右到左）扫描，利用树状数组查询已扫描元素中比当前元素大（或小）的元素个数（即新增的逆序对数）。
-
动态区间更新 + 单点查询： 利用差分思想。令
diff[i] = arr[i] - arr[i-1]（arr[0]=0），构建diff数组的树状数组。-
区间更新
[l, r] + delta：update(l, delta); update(r+1, -delta); -
单点查询
arr[i]：query(i)(等于diff[1]+...+diff[i]，即arr[i])
-
-
动态区间更新 + 区间和查询： 需要两个树状数组（维护差分数组
diff[i]和i * diff[i]），推导稍复杂。 -
求第 K 小/大元素（权值树状数组）： 配合离散化，将元素值作为下标，在树状数组中进行计数。通过二分查找前缀和
>=k的最小位置。
-
核心思想：
-
分块存储前缀和信息： 不是直接存储原始数组
arr，也不是存储所有前缀和，而是存储一个辅助数组tree。 -
利用二进制表示：
tree数组的索引i的二进制表示决定了它存储哪些arr元素的和。具体来说：-
tree[i] = arr[j] + arr[j+1] + ... + arr[i]，其中j = i - lowbit(i) + 1。
-
-
Lowbit 函数： 这是树状数组的灵魂。
lowbit(i)表示数字i的二进制表示中最低位的1及其后面的0所构成的数值。计算公式：-
lowbit(i) = i & (-i)（利用补码特性）
-
-
-
结构特点：
-
数组下标通常从 1 开始（
arr[1..n],tree[1..n]）。下标0不使用。 -
tree[i]负责的区间长度等于lowbit(i)。 -
tree[i]的父节点是tree[i + lowbit(i)]。 -
tree[i]的子节点包括tree[i - 2^k]（其中2^k < lowbit(i)，且k从0开始递增直到i - 2^k > i - lowbit(i)）。这些节点构成了tree[i]覆盖范围的一部分。
-
优势与局限
-
优势：
-
代码极其简洁（核心函数通常只需几行）。
-
效率高（O(log n)），常数因子小。
-
内存占用小（O(n)）。
-
-
局限：
-
主要解决前缀和相关问题（和、计数）。虽然可以通过技巧实现区间更新、最值（效率较低且复杂）等，但不如线段树直观和通用。
-
无法高效处理任意区间上的非和操作（如区间最大值/最小值、区间乘积、复杂的区间合并信息）。
-
下标通常需要从 1 开始。
-
模板:
lowbit:
lowbit(i) 表示数字 i 的二进制表示中最低位的 1 及其后面的 0 所构成的数值。
计算公式：
lowbit(i) = i & -i;
计算原理：
-
-i是i的补码（按位取反后加 1） -
i & -i会保留i的最低位 1，其余位变为 0
为什么 lowbit(i) 如此重要？
-
高效性：
-
更新和查询操作只需 O(log n) 时间
-
每次操作最多访问 log₂(n) 个节点
-
-
内存效率：
-
仅需 O(n) 额外空间
-
比线段树更紧凑（线段树需要 4n 空间）
-
-
操作对称性：
-
更新操作：
i += lowbit(i)（向上） -
查询操作：
i -= lowbit(i)（向左）
-
-
定义数据结构本质：
-
决定了每个节点存储的区间范围
-
建立了节点间的层级关系
-
核心代码：
int n, m; // n为数组长度，m为操作次数
int a[500005]; // 树状数组存储结构// 计算x的最低位1对应的数值（lowbit操作）
// 例如：x=6(110)，-x=1010，x&(-x)=10(2)
int lowbit(int x) {return x & (-x);
}// 向树状数组的第i个位置添加值w（单点更新操作）
// 时间复杂度：O(log n)
void add(int i, int w) {/* 递归实现if (i <= n) {a[i] += w;add(i + lowbit(i), w);}*/// 迭代实现while (i <= n) {a[i] += w; // 更新当前节点i += lowbit(i); // 向上更新父节点（跳转到下一个覆盖当前位置的节点）}
}// 计算从1到i的前缀和（区间查询操作）
// 时间复杂度：O(log n)
int count(int i) {/* 递归实现if (i <= 0) {return 0;}return count(i - lowbit(i)) + a[i];*/// 迭代实现int result = 0;while (i > 0) {result += a[i]; // 累加当前节点的值i -= lowbit(i); // 向下查询子节点（跳转到上一个不覆盖当前位置的节点）}return result;
}例题：
树状数组 1
#define _CRT_SECURE_NO_WARNINGS
#include<stdio.h>
#include<iostream>
#include<bits/stdc++.h>
using namespace std;
int n, m;
int a[500005];
int lowbit(int x) {return x & (-x);
}
void add(int i, int w) {/*if (i <= n) {a[i] += w;add(i + lowbit(i), w);}*///或while (i <= n) {a[i] += w;i += lowbit(i);}
}
int count(int i) {/*if (i <= 0) {return 0;}return count(i - lowbit(i)) + a[i];*///或int result = 0;while (i > 0) {result += a[i];i -= lowbit(i);}return result;
}
int main(){ios::sync_with_stdio(false); // 禁用同步cin.tie(nullptr); // 解除cin与cout绑定cin >> n >> m;int w;for (int i = 1; i <= n; i++) {cin >> w;add(i, w);}int h, x, k;for (int i = 1; i <= m; i++) {cin >> h >> x >> k;if (h == 1) {add(x, k);}else {cout << count(k) - count(x-1) << endl;}}return 0;
}