第 28 章 树状数组与ST表 · 知识细节练习

树状数组（Fenwick Tree）主要解决？

$\mathrm{lowbit}(x)$ 的定义是？

树状数组中节点 $i$ 负责维护的区间是？

树状数组与线段树的正确对比是？

判断题：树状数组只支持"可差分"的操作（如区间和 = 前缀和之差）——区间最值不可差分，不能用树状数组做。

判断题：树状数组必须下标 1 起——因为 lowbit 运算依赖下标，0 下标会死循环。

lowbit 的代码实现是？

判断题：$\mathrm{lowbit}(x)$ 恒为 2 的幂，且 $x - \mathrm{lowbit}(x)$ 恰好去掉最低位的 1。

$\mathrm{lowbit}(6) = 2$，节点 6 维护的区间是？

$1 \sim 8$ 的 lowbit 序列是？

判断题：树状数组按 lowbit 形成层次——节点 8 管 $[1,8]$、节点 4 管 $[1,4]$、节点 6 管 $[5,6]$——区间层层覆盖不重不漏。

lowbit 的经典应用是？

判断题：树状数组用"二进制分解"把前缀 $[1, x]$ 拆成 $O(\log n)$ 段——每段对应一个节点，这是它 $O(\log n)$ 的根源。

树状数组单点加 add(i, v) 的循环是？

$n = 8$ 时，add(3, v) 更新哪些节点？

树状数组前缀查询 sum(x) 的循环是？

$n = 8$ 时，sum(6) 累加哪些节点？

树状数组单点修改的复杂度是？

树状数组前缀查询的复杂度是？

判断题：add 沿"往上跳"（i += lowbit）更新所有包含它的节点；sum 沿"往下跳"（i -= lowbit）收集覆盖前缀的节点——方向相反。

树状数组求区间 $[l, r]$ 的和的公式是？

用差分 + 树状数组实现"区间加、单点查"的做法是？

判断题：区间加 + 区间查需要两个树状数组（一个维护 diff、一个维护 i×diff）——利用前缀和公式拆解。

树状数组求逆序对的思路是？

判断题：值域很大（如 $10^9$）时树状数组下标开不下——先离散化把值映射到排名再建树。

下列哪个操作能用树状数组（含差分技巧）实现？

判断题：树状数组通过"差分 + 前缀和分解"能覆盖大部分区间修改查询问题——但最值类操作仍需要线段树。

ST 表（Sparse Table）解决什么问题？

ST 表的倍增思想是？

$\mathrm{st}[i][j]$ 表示？

ST 表建表的时间复杂度是？

ST 表单次查询的复杂度是？

ST 表与线段树的正确对比是？

ST 表建表的递推公式是？

判断题：查询 $[l, r]$ 取 $k = \lfloor \log_2(r-l+1) \rfloor$，用 $[l, l+2^k-1]$ 与 $[r-2^k+1, r]$ 两段重叠覆盖整个区间——重叠无害（最值幂等）。

判断题：log 值预处理 lg[i] = lg[i/2] + 1——查询时 $O(1)$ 取到 $k$。

查询 $[2, 6]$（长度 5）时 $k$ 取？

ST 表查询 $[l, r]$ 的公式是？

判断题：ST 表实现三件套 = 建表递推（倍增合并）+ log 预处理 + 查询两段覆盖——缺一不可。

线段树、树状数组、ST 表的总表是？

静态 RMQ（不修改）最佳选择是？

判断题：树状数组应用总表——单点改区间查、区间改单点查（差分）、区间改区间查（双树状数组）、逆序对、第 k 小（倍增思想）。

判断题：ST 表应用总表——静态 RMQ、区间 gcd（幂等运算皆可）、LCA 预处理思想——一切幂等且静态的区间查询。

判断题：三结构按"功能 × 速度"权衡——ST 表最快最受限、树状数组最轻量、线段树最全面。

需要"单点修改 + 区间和查询"，代码要短，选？

判断题：lowbit 写成 x & (x - 1) 是"去掉最低位 1"（不是 lowbit）——循环会跳错。

判断题：树状数组下标 0 起会死循环——0 + lowbit(0) = 0 永远跳不上去。

判断题：ST 表查询的两段是 $[l, l+2^k-1]$ 与 $[r-2^k+1, r]$——第二段起点写成 $r-2^k$ 会漏掉 r。

判断题：区间加 [l,r] 的差分是 diff[l] += v、diff[r+1] -= v——两处符号写反会导致整个区间错。

判断题：以下结论全部正确——"lowbit 用 x&-x；add 往上跳、sum 往下跳；下标必须 1 起；ST 表查询两段重叠覆盖；差分区间加是 l 加 r+1 减"。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 6;                   // 110 的二进制
05    cout << (x & (-x));          // lowbit
06    return 0;
07}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    for (int i = 1; i <= 8; i++) cout << (i & (-i)) << " ";
05    return 0;
06}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int i = 6;
05    int lb = i & (-i);
06    cout << i - lb + 1 << " " << i;   // 节点 6 管的区间 [左端点, 右端点]
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 12;
05    cout << ______;              // lowbit(12) = 4
06    return 0;
07}

单选题：横线处应填入？（使输出为 4）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 6;                   // 110
05    int y = x - (x & (-x));      // 去掉最低位 1
06    cout << y;                   // 100 = 4
07    return 0;
08}

单选题：程序输出是？

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 20;                  // 10100
05    int cnt = 0;
06    while (x) { x -= (x & (-x)); cnt++; }   // 数二进制中 1 的个数
07    cout << cnt;
08    return 0;
09}

单选题：程序输出是？（20 = 10100 有 2 个 1）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int i = 3, n = 8;
05    while (i <= n) {
06        cout << i << " ";
07        i += (i & (-i));         // add 的跳转
08    }
09    return 0;
10}

单选题：程序输出是？（add(3) 更新的节点路径）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 6;
05    while (x > 0) {
06        cout << x << " ";
07        x -= (x & (-x));         // sum 的跳转
08    }
09    return 0;
10}

单选题：程序输出是？（sum(6) 累加的节点路径）

01#include <bits/stdc++.h>
02using namespace std;
03int a[9] = {0, 1, 3, 5, 7, 9, 11, 13, 15};
04int c[9] = {0};
05int main() {
06    for (int i = 1; i <= 8; i++) {               // 建树：逐点 add
07        int j = i;
08        while (j <= 8) { c[j] += a[i]; j += (j & (-j)); }
09    }
10    int x = 6, s = 0;
11    while (x > 0) { s += c[x]; x -= (x & (-x)); }   // sum(6)
12    cout << s;
13    return 0;
14}

单选题：程序输出是？（前 6 项和 = 1+3+5+7+9+11）

01#include <bits/stdc++.h>
02using namespace std;
03int a[9] = {0, 1, 3, 5, 7, 9, 11, 13, 15};
04int c[9] = {0};
05int main() {
06    for (int i = 1; i <= 8; i++) {
07        int j = i;
08        while (j <= 8) { c[j] += a[i]; j += (j & (-j)); }
09    }
10    int p = 3, v = 2;                            // a[3] += 2
11    while (p <= 8) { c[p] += v; p += (p & (-p)); }
12    int x = 6, s = 0;
13    while (x > 0) { s += c[x]; x -= (x & (-x)); }
14    cout << s;
15    return 0;
16}

单选题：程序输出是？（a[3] 加 2 后前 6 项和 = 36 + 2）

01#include <bits/stdc++.h>
02using namespace std;
03int c[9] = {0, 1, 4, 5, 16, 9, 20, 13, 64};
04void add(int i, int v) {
05    while (i <= 8) { c[i] += v; i += ______; }    // lowbit 上跳
06}
07int sum(int x) {
08    int s = 0;
09    while (x > 0) { s += c[x]; x -= ______; }      // lowbit 下跳
10    return s;
11}
12int main() {
13    add(5, 10);                     // a[5] += 10
14    cout << sum(5);
15    return 0;
16}

单选题：两处横线应填入？（使输出为 35——add(5) 更新 c[5]、c[6]、c[8]，sum(5) = c[5]+c[4] = 19+16）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 建树 + 两次修改 + 区间查询
05    int a[9] = {0, 2, 4, 6, 8, 10, 12, 14, 16};
06    int c[9] = {0};
07    for (int i = 1; i <= 8; i++) {
08        int j = i;
09        while (j <= 8) { c[j] += a[i]; j += (j & (-j)); }
10    }
11    for (int p : {2, 5}) {                  // a[2] += 1、a[5] += 1
12        int j = p;
13        while (j <= 8) { c[j] += 1; j += (j & (-j)); }
14    }
15    auto sum = [&](int x) { int s = 0; while (x > 0) { s += c[x]; x -= (x & (-x)); } return s; };
16    cout << sum(6) - sum(2);                 // [3,6] 的和
17    return 0;
18}

单选题：程序输出是？（原 [3,6] = 6+8+10+12 = 36，a[5] 在区间内 +1 → 37）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[9] = {0, 1, 3, 5, 7, 9, 11, 13, 15};
05    int c[9] = {0};
06    for (int i = 1; i <= 8; i++) {
07        int j = i;
08        while (j <= 8) { c[j] += a[i]; j += (j & (-j)); }
09    }
10    auto sum = [&](int x) { int s = 0; while (x > 0) { s += c[x]; x -= (x & (-x)); } return s; };
11    cout << sum(6) - sum(2);      // [3,6] 的和 = 36 - 4
12    return 0;
13}

单选题：程序输出是？（[3,6] = 5+7+9+11）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 5;
05    int diff[6] = {0, 1, 0, 0, 0, 0};   // 初始 a 全 1 的差分（a[i]=a[i-1]+diff[i]）
06    // 区间 [2,4] +3：diff[2] += 3、diff[5] -= 3
07    diff[2] += 3; diff[5] -= 3;
08    int x = 3, s = 0;                  // 查 a[3] = 前缀和
09    for (int i = 1; i <= x; i++) s += diff[i];
10    cout << s;
11    return 0;
12}

单选题：程序输出是？（a[3] = 1 + 3 = 4）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 区间加 + 区间查：双树状数组（此处直接模拟最终效果）
05    // 初始 {1,1,1,1,1}，[1,3] +2、[3,5] +1 → {2,2,3,1,1}（注意 d 是"增量"）
06    int a[6] = {0, 1, 1, 1, 1, 1};
07    int d[7] = {0};
08    d[1] += 2; d[4] -= 2;      // [1,3] +2
09    d[3] += 1; d[6] -= 1;      // [3,5] +1
10    for (int i = 1; i <= 5; i++) { a[i] = a[i - 1] + d[i]; cout << a[i] << " "; }
11    return 0;
12}

单选题：程序输出是？（差分前缀和还原后的数组）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {3, 1, 4, 2};
05    long long cnt = 0;
06    // 朴素模拟（树状数组加速版同理）：统计前面大于 a[i] 的个数
07    for (int i = 0; i < 4; i++)
08        for (int j = 0; j < i; j++)
09            if (a[j] > a[i]) cnt++;
10    cout << cnt;
11    return 0;
12}

单选题：程序输出是？（{3,1,4,2} 的逆序对）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[4] = {100, 5, 99999, 50};
05    int b[4];
06    for (int i = 0; i < 4; i++) b[i] = a[i];
07    sort(b, b + 4);                     // {5, 50, 100, 99999}
08    for (int i = 0; i < 4; i++)
09        cout << lower_bound(b, b + 4, a[i]) - b + 1 << " ";   // 排名（1 起）
10    return 0;
11}

单选题：程序输出是？（离散化后的排名）

01#include <bits/stdc++.h>
02using namespace std;
03int c[9] = {0, 1, 4, 5, 16, 9, 20, 13, 64};
04int sum(int x) {
05    int s = 0;
06    while (x > 0) { s += c[x]; x -= (x & (-x)); }
07    return s;
08}
09int main() {
10    int l = 3, r = 6;
11    cout << ______;              // 区间和公式
12    return 0;
13}

单选题：横线处应填入？（使输出为 32）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 差分 + 树状数组：区间加 [2,6] +5 后查 [3,5] 的和
05    int a[9] = {0};            // 初始全 0
06    int d[10] = {0};
07    d[2] += 5; d[7] -= 5;      // [2,6] +5
08    for (int i = 1; i <= 8; i++) a[i] = a[i - 1] + d[i];
09    int s = 0;
10    for (int i = 3; i <= 5; i++) s += a[i];
11    cout << s;
12    return 0;
13}

单选题：程序输出是？（[3,5] 内都是 +5 → 15）

01#include <bits/stdc++.h>
02using namespace std;
03int st[9][4];
04int main() {
05    int a[9] = {0, 2, 4, 6, 8, 10, 12, 14, 16};
06    for (int i = 1; i <= 8; i++) st[i][0] = a[i];   // j = 0 层
07    for (int j = 1; (1 << j) <= 8; j++)
08        for (int i = 1; i + (1 << j) - 1 <= 8; i++)
09            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
10    for (int j = 0; j <= 3; j++) cout << st[1][j] << " ";
11    return 0;
12}

单选题：程序输出是？（st[1][0..3]——从 1 开始长度 1/2/4/8 的最值）

01#include <bits/stdc++.h>
02using namespace std;
03int st[9][4];
04int main() {
05    int a[9] = {0, 2, 4, 6, 8, 10, 12, 14, 16};
06    for (int i = 1; i <= 8; i++) st[i][0] = a[i];
07    for (int j = 1; (1 << j) <= 8; j++)
08        for (int i = 1; i + (1 << j) - 1 <= 8; i++)
09            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
10    int l = 2, r = 7;
11    int k = log2(r - l + 1);                     // 长度 6 → k = 2
12    cout << max(st[l][k], st[r - (1 << k) + 1][k]);
13    return 0;
14}

单选题：程序输出是？（[2,7] = {4,6,8,10,12,14} 的最大值）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int lg[9] = {0};
05    for (int i = 2; i <= 8; i++) lg[i] = lg[i / 2] + 1;
06    for (int i = 1; i <= 8; i++) cout << lg[i] << " ";
07    return 0;
08}

单选题：程序输出是？（1~8 的 floor(log2)）

01#include <bits/stdc++.h>
02using namespace std;
03int st[9][4];
04int main() {
05    int a[9] = {0, 2, 4, 6, 8, 10, 12, 14, 16};
06    for (int i = 1; i <= 8; i++) st[i][0] = a[i];
07    for (int j = 1; (1 << j) <= 8; j++)
08        for (int i = 1; i + (1 << j) - 1 <= 8; i++)
09            st[i][j] = ______;         // 两半取最大
10    cout << st[1][3];
11    return 0;
12}

单选题：横线处应填入？（使输出为 16）

01#include <bits/stdc++.h>
02using namespace std;
03int st[9][4];
04int main() {
05    int a[9] = {0, 2, 4, 6, 8, 10, 12, 14, 16};
06    for (int i = 1; i <= 8; i++) st[i][0] = a[i];
07    for (int j = 1; (1 << j) <= 8; j++)
08        for (int i = 1; i + (1 << j) - 1 <= 8; i++)
09            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
10    int l = 1, r = 5;
11    int k = log2(r - l + 1);                     // 长度 5 → k = 2
12    cout << max(st[l][k], ______);               // 第二段起点 r - 2^k + 1
13    return 0;
14}

单选题：横线处应填入？（使输出为 10——[1,5] 最大）

01#include <bits/stdc++.h>
02using namespace std;
03int st[9][4];
04int main() {
05    int a[9] = {0, 3, 1, 4, 1, 5, 9, 2, 6};
06    for (int i = 1; i <= 8; i++) st[i][0] = a[i];
07    for (int j = 1; (1 << j) <= 8; j++)
08        for (int i = 1; i + (1 << j) - 1 <= 8; i++)
09            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
10    int l = 3, r = 6;
11    int k = log2(r - l + 1);                     // 长度 4 → k = 2
12    cout << max(st[l][k], st[r - (1 << k) + 1][k]);
13    return 0;
14}

单选题：程序输出是？（[3,6] = {4,1,5,9} 的最大值）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 静态 RMQ → ST 表；单点改区间查 → 树状数组；区间改区间查最值 → 线段树
05    cout << "ST / BIT / SEGTREE";
06    return 0;
07}

判断题：静态 RMQ 选 ST 表、单点改区间查选树状数组、区间改区间查最值选线段树——该选择全部合理。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 树状数组核心只有两个函数（add 与 sum）共约 10 行；
05    // 线段树（含 lazy）核心约 40 行
06    cout << "BIT shorter";
07    return 0;
08}

判断题：实现"单点修改 + 区间求和"，树状数组代码量远小于线段树且常数更小——能用树状数组就优先用它。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // ST 表建好后不支持单点修改——改一个元素可能影响 O(n log n) 个状态
05    cout << "static only";
06    return 0;
07}

判断题：ST 表是静态结构——元素修改后需 $O(n \log n)$ 重建，因此只适合"建一次查多次"的场景。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 问题：区间最大公约数（gcd 幂等）+ 不修改 → ST 表
05    cout << "ST";
06    return 0;
07}

判断题：区间 gcd 是幂等运算（gcd(x,x)=x），静态查询可用 ST 表（把 max 换成 gcd）——ST 表不止能做最值。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int n = 100000;
05    // 线段树/树状数组：O(n) 建 + O(log n) 每次
06    // ST 表：O(n log n) 建 + O(1) 每次
07    cout << n * (int)log2(n);
08    return 0;
09}

判断题：ST 表建表 $O(n \log n)$（此处 $10^5 \times 16$）比线段树建树 $O(n)$ 贵，但查询 $O(1)$ 更快——用建表时间换查询时间。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 选择流程：① 要修改吗？→ 是：线段树/树状数组；否：ST 表
05    // ② 操作可差分吗？→ 是：树状数组；否：线段树
06    cout << "flow ok";
07    return 0;
08}

判断题：按"改不改 → 可不可差分"两步选型，能覆盖绝大多数区间问题。

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int a[5] = {5, 3, 1, 4, 2};
05    long long cnt = 0;
06    for (int i = 0; i < 5; i++)
07        for (int j = 0; j < i; j++)
08            if (a[j] > a[i]) cnt++;
09    cout << cnt;
10    return 0;
11}

单选题：程序输出是？（{5,3,1,4,2} 的逆序对）

01#include <bits/stdc++.h>
02using namespace std;
03int st[9][4];
04int main() {
05    int a[9] = {0, 7, 2, 9, 4, 6, 1, 8, 3};
06    for (int i = 1; i <= 8; i++) st[i][0] = a[i];
07    for (int j = 1; (1 << j) <= 8; j++)
08        for (int i = 1; i + (1 << j) - 1 <= 8; i++)
09            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
10    int l = 4, r = 7;
11    int k = log2(r - l + 1);
12    cout << max(st[l][k], st[r - (1 << k) + 1][k]);
13    return 0;
14}

单选题：程序输出是？（[4,7] = {4,6,1,8} 的最大值）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 树状数组求第 k 小：二分 + 前缀和（此处直接演示二分查排名）
05    int cnt[9] = {0, 1, 0, 1, 1, 0, 1, 0, 0};   // 值 1、3、4、6 各 1 个
06    // 求第 3 小：前缀和第一个 >= 3 的位置
07    int k = 3, s = 0, ans = 0;
08    for (int i = 1; i <= 8; i++) {
09        s += cnt[i];
10        if (s >= k) { ans = i; break; }
11    }
12    cout << ans;
13    return 0;
14}

单选题：程序输出是？（第 3 小的值）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    // 差分：对 [2,5] +4 后，求整个数组（初始全 0）的元素
05    int a[7] = {0};
06    int d[8] = {0};
07    d[2] += 4; d[6] -= 4;      // [2,5] +4
08    for (int i = 1; i <= 6; i++) a[i] = a[i - 1] + d[i];
09    cout << a[3] << " " << a[6];
10    return 0;
11}

单选题：程序输出是？（a[3] = 4、a[6] = 0）

01#include <bits/stdc++.h>
02using namespace std;
03int main() {
04    int x = 6, s = 0;
05    while (x > 0) { s += x % 2; ______; }   // 数二进制 1 的个数
06    cout << s;
07    return 0;
08}

单选题：横线处应填入？（使输出为 2——6 = 110 有两个 1）

01#include <bits/stdc++.h>
02using namespace std;
03int st[9][4];
04int main() {
05    int a[9] = {0, 1, 5, 2, 8, 3, 9, 4, 7};
06    for (int i = 1; i <= 8; i++) st[i][0] = a[i];
07    for (int j = 1; (1 << j) <= 8; j++)
08        for (int i = 1; i + (1 << j) - 1 <= 8; i++)
09            st[i][j] = max(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
10    int l = 1, r = 8;
11    int k = log2(r - l + 1);       // k = 3
12    cout << max(st[l][k], st[r - (1 << k) + 1][k]);
13    return 0;
14}

单选题：程序输出是？（全区间 [1,8] 的最大值）