《树状数组》

1. 解决的问题：

   • 维护一个长度为 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）：离散化 + 树状数组统计。

2. 应用场景总结

• 动态单点修改 + 区间和查询： 最直接的应用。

• 动态逆序对计数： 离散化原始数据，然后从左到右（或从右到左）扫描，利用树状数组查询已扫描元素中比当前元素大（或小）的元素个数（即新增的逆序对数）。

• 动态区间更新 + 单点查询： 利用差分思想。令 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 的最小位置。

1. 核心思想：

   1. 分块存储前缀和信息： 不是直接存储原始数组 arr，也不是存储所有前缀和，而是存储一个辅助数组 tree。

   2. 利用二进制表示： tree 数组的索引 i 的二进制表示决定了它存储哪些 arr 元素的和。具体来说：

      1. tree[i] = arr[j] + arr[j+1] + ... + arr[i]，其中 j = i - lowbit(i) + 1。

   3. Lowbit 函数： 这是树状数组的灵魂。lowbit(i) 表示数字 i 的二进制表示中最低位的 1 及其后面的 0 所构成的数值。计算公式：

      1. lowbit(i) = i & (-i) （利用补码特性）

2. 结构特点：

   1. 数组下标通常从 1 开始（arr[1..n], tree[1..n]）。下标 0 不使用。

   2. tree[i] 负责的区间长度等于 lowbit(i)。

   3. tree[i] 的父节点是 tree[i + lowbit(i)]。

   4. 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) 如此重要？

1. 高效性：

   • 更新和查询操作只需 O(log n) 时间

   • 每次操作最多访问 log₂(n) 个节点

2. 内存效率：

   • 仅需 O(n) 额外空间

   • 比线段树更紧凑（线段树需要 4n 空间）

3. 操作对称性：

   • 更新操作：i += lowbit(i)（向上）

   • 查询操作：i -= lowbit(i)（向左）

4. 定义数据结构本质：

   • 决定了每个节点存储的区间范围

   • 建立了节点间的层级关系

核心代码：

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;
}