# C++11 高级数据结构（静态数组模拟版）讲义

在解决算法竞赛（如 CSP-S、NOI）中的高难度问题时，使用**指针与结构体动态分配内存**常面临执行效率低（因频繁申请堆内存）及容易出现内存泄露或段错误等风险。

本讲义严格基于 **C++11 标准**，所有高级数据结构全部采用**静态一维/多维平行数组**进行模拟。这样不仅能将运行速度提升至接近硬件极限，而且代码结构极为规整，便于调试与维护。

---

## 1. 线性结构

### 1.1 双端栈 (Double-ended Stack)
双端栈是指两个栈共享同一个一维数组空间。一个栈顶设在数组的左端点（向右增长），另一个栈顶设在数组的右端点（向左增长）。

#### 1. 结构设计与边界
设数组大小为 $N$，左栈顶为 `top1`，右栈顶为 `top2`：
*   **初始状态**：`top1 = -1`, `top2 = N`
*   **栈满条件**：`top1 + 1 == top2`

#### 2. C++11 实现
```cpp
constexpr int N = 100010;
int destk[N];
int top1 = -1, top2 = N;

void push1(int x) {
    if (top1 + 1 < top2) destk[++top1] = x;
}

void push2(int x) {
    if (top1 + 1 < top2) destk[--top2] = x;
}

void pop1() {
    if (top1 >= 0) top1--;
}

void pop2() {
    if (top2 < N) top2++;
}
```

---

### 1.2 双端队列 (Double-ended Queue / Deque)
双端队列允许在队列的两端进行插入与删除。我们利用一个足够大的静态数组与两个指针 `hh`（头指针）和 `tt`（尾指针）来模拟。
```cpp
int deq[N * 2]; // 空间开双倍，防止向左或向右单向溢出
int hh = N, tt = N - 1; // 初始位置设在数组中心

void push_back(int x) {
    deq[++tt] = x;
}

void push_front(int x) {
    deq[--hh] = x;
}

void pop_back() {
    if (hh <= tt) tt--;
}

void pop_front() {
    if (hh <= tt) hh++;
}
```

---

### 1.3 单调队列 (Monotonic Queue)

单调队列是一种维护其内部元素具有单调性（递增或递减）的双端队列。其最经典的应用是解决**滑动窗口最值问题**。

#### 1. 算法复杂度证明
设序列长度为 $n$，滑动窗口大小为 $k$：
*   **定理**：单调队列求解滑动窗口最值的时间复杂度为 $O(n)$。
*   **证明**：在整个处理流程中，序列中的每个元素 $i$ 最多只会执行一次入队（通过 `tt++`）和至多一次出队（通过 `hh++` 或 `tt--`）。因为入队和出队的总次数均不超过 $n$，所以总时间复杂度在均摊意义下为 $O(n)$。

#### 2. C++11 实现：滑动窗口最小值
```cpp
int a[N]; // 原序列
int q[N]; // 存储原序列的下标而非数值
int hh = 0, tt = -1;

void sliding_window_min(int n, int k) {
    hh = 0, tt = -1;
    for (int i = 0; i < n; ++i) {
        // 1. 判断队头元素是否滑出窗口
        if (hh <= tt && q[hh] < i - k + 1) hh++;
        
        // 2. 保持队列单调递增：若新加入的值 a[i] 小于等于队尾对应的元素，则将队尾弹出
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;
        
        // 3. 将当前元素的下标压入队列
        q[++tt] = i;
        
        // 4. 当窗口形成后，队头即为当前窗口的最小值
        if (i >= k - 1) {
            std::cout << a[q[hh]] << " ";
        }
    }
}
```

---

### 1.4 静态二叉堆（优先队列）

堆是一个完全二叉树。我们采用一维数组进行物理映射存储，索引从 $1$ 开始：
*   若节点索引为 $u$，则左孩子为 $2u$，右孩子为 $2u+1$，双亲为 $\lfloor u/2 \rfloor$。

#### C++11 实现（小顶堆）
```cpp
int heap[N], heap_size = 0;

void down(int u) {
    int t = u;
    if (u * 2 <= heap_size && heap[u * 2] < heap[t]) t = u * 2;
    if (u * 2 + 1 <= heap_size && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
    if (u != t) {
        std::swap(heap[u], heap[t]);
        down(t);
    }
}

void up(int u) {
    while (u / 2 && heap[u / 2] > heap[u]) {
        std::swap(heap[u / 2], heap[u]);
        u /= 2;
    }
}

void push(int x) {
    heap[++heap_size] = x;
    up(heap_size);
}

void pop() {
    heap[1] = heap[heap_size--];
    down(1);
}

int top() {
    return heap[1];
}
```

---

### 1.5 ST 表 (Sparse Table)
ST 表用于解决区间最值查询（RMQ）问题。其基于倍增和动态规划思想。

#### 1. 状态转移
$f[i][j]$ 表示以 $i$ 为起点，长度为 $2^j$ 的区间内的最值。由于区间可以重叠且最值操作满足幂等性（即 $\max(x, x) = x$），查询区间 $[L, R]$ 时，设其跨度长度的对数为 $k = \lfloor \log\_2(R-L+1) \rfloor$，则有：
$$\text{RMQ}(L, R) = \max(f[L][k], f[R - 2^k + 1][k])$$

#### 2. C++11 预处理与查询
```cpp
#include <algorithm>

int f[N][20];
int lg[N];

void init_st_table(int arr[], int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;
    
    for (int i = 1; i <= n; ++i) f[i][0] = arr[i];
    
    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query_st(int l, int r) {
    int k = lg[r - l + 1];
    return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}
```

---

## 2. 集合与森林

### 2.1 并查集 (Disjoint Set Union, DSU)

并查集用于处理集合的合并与查询。

#### 1. 路径压缩优化复杂度
在并查集中，如果不进行任何优化，退化的树形结构会导致单次查询的时间复杂度退化为 $O(n)$。
通过**路径压缩（Path Compression）**，在每次执行查找根节点操作时，将路径上所有遇到的节点直接挂载到根节点上。

*   **定理**：结合路径压缩与按秩合并（或大小合并）的并查集，单次操作的均摊时间复杂度为 $O(\alpha(n))$，其中 $\alpha$ 为反阿克曼函数，是一个增长极其缓慢的函数（对所有实际物理数值，$\alpha(n) \le 4$）。

#### 2. C++11 实现
```cpp
int p[N]; // 记录每个节点的双亲

void init_dsu(int n) {
    for (int i = 1; i <= n; ++i) p[i] = i;
}

// 包含路径压缩的查找根节点函数
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); // 递归压缩路径
    return p[x];
}

// 合并操作
void merge(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        p[root_x] = root_y;
    }
}
```

---

### 2.2 树的孩子兄弟表示法
对于一般的多叉树，如果不通过结构体指针表示，可以通过静态一维数组模拟：
*   `first_child[u]`：存储节点 $u$ 的第一个长子。
*   `next_sibling[u]`：存储节点 $u$ 紧邻的下一个右侧兄弟节点。

```cpp
int first_child[N], next_sibling[N];

void init_tree_nodes(int n) {
    std::fill(first_child, first_child + n + 1, -1);
    std::fill(next_sibling, next_sibling + n + 1, -1);
}

// 给节点 u 添加子节点 v
void add_child(int u, int v) {
    if (first_child[u] == -1) {
        first_child[u] = v;
    } else {
        int curr = first_child[u];
        while (next_sibling[curr] != -1) {
            curr = next_sibling[curr];
        }
        next_sibling[curr] = v;
    }
}
```

---

## 3. 特殊树结构

### 3.1 树状数组 (Fenwick Tree / Binary Indexed Tree)

树状数组常用于高效计算区间的动态单点修改与前缀和查询。

#### 1. `lowbit` 机制证明
设一个正整数 $x$ 的二进制表示为 $x = \text{bin\_arr} \cdot 2^k$。其 `lowbit` 定义为取出 $x$ 二进制表示中最低位的 $1$ 及其后面的 $0$：
$$\text{lowbit}(x) = x \ \& \ (-x)$$

*   **证明**：在计算机中，负数以补码形式存储。设 $x$ 的二进制最低位 1 出现在第 $k$ 位，则：
    $$x = \dots 1 \underbrace{0 \dots 0}\_{k \text{ 个 } 0}$$
    其反码 $\sim x$ 将该最低位的 1 变为 0，后面的 0 均变为 1。
    其补码 $-x = \sim x + 1$ 会导致最低位右侧的所有 1 产生进位，从而使原第 $k$ 位重新变回 1，且其右侧所有位重置为 0。
    对 $x$ 与 $-x$ 进行按位与 `&` 运算后，第 $k$ 位左侧因为按位反转全部归 0，右侧也为 0，只有第 $k$ 位保持为 1。因此，结果恰好为 $2^k$。

#### 2. C++11 实现
```cpp
int tr[N];
int limit_n;

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

// 单点增加 c
void add(int x, int c) {
    for (int i = x; i <= limit_n; i += lowbit(i)) tr[i] += c;
}

// 查询前缀和 [1, x]
int query(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) sum += tr[i];
    return sum;
}
```

---

### 3.2 线段树 (Segment Tree)

线段树用于维护区间上的合并信息，支持区间修改与区间查询。通过**懒标记 (Lazy Tag)**，可以将区间更新的均摊时间复杂度降至 $O(\log n)$。

```cpp
// 静态线段树：空间需要开辟原序列大小的 4 倍
int sum_tr[N * 4], lazy[N * 4];

void pushup(int u) {
    sum_tr[u] = sum_tr[u << 1] + sum_tr[u << 1 | 1];
}

void pushdown(int u, int l, int r) {
    if (lazy[u]) {
        int mid = l + (r - l) / 2;
        // 分发懒标记
        lazy[u << 1] += lazy[u];
        sum_tr[u << 1] += lazy[u] * (mid - l + 1);
        
        lazy[u << 1 | 1] += lazy[u];
        sum_tr[u << 1 | 1] += lazy[u] * (r - mid);
        
        lazy[u] = 0; // 清除当前标记
    }
}

// 区间修改：[L, R] 统一加上 val
void update(int u, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
        sum_tr[u] += val * (r - l + 1);
        lazy[u] += val;
        return;
    }
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    if (L <= mid) update(u << 1, l, mid, L, R, val);
    if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, val);
    pushup(u);
}

// 区间查询：求 [L, R] 内的元素和
int query(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum_tr[u];
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    int res = 0;
    if (L <= mid) res += query(u << 1, l, mid, L, R);
    if (R > mid) res += query(u << 1 | 1, mid + 1, r, L, R);
    return res;
}
```

---

### 3.3 字典树 (Trie)
字典树又称前缀树，用于高效存储和检索字符串集合。

```cpp
int son[N][26]; // 26个英文字母分支
int cnt[N];     // 记录以当前节点结尾的单词数量
int trie_idx;   // 静态分配节点

void trie_insert(const char* str) {
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++trie_idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int trie_query(const char* str) {
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}
```

---

### 3.4 笛卡尔树 (Cartesian Tree)

笛卡尔树是一棵二叉树，每个节点存储一个二元组 $(key, val)$：
1. 其关于键值 $key$ 满足**二叉搜索树**的性质。
2. 其关于权值 $val$ 满足**堆**的性质。

当 $key$ 递增时（如一维数组的索引），笛卡尔树可以在 **$O(n)$ 线性时间**内利用单调栈构建完成。

#### C++11 实现
```cpp
int tree_l[N], tree_r[N], val[N];
int mono_stk[N], stk_top;

// 构建笛卡尔树并返回根节点
int build_cartesian_tree(int n) {
    stk_top = 0;
    std::fill(tree_l, tree_l + n + 1, 0);
    std::fill(tree_r, tree_r + n + 1, 0);

for (int i = 1; i <= n; ++i) {
        int last = 0;
        // 维持栈内元素权值单调递增（小顶堆）
        while (stk_top > 0 && val[mono_stk[stk_top]] > val[i]) {
            last = mono_stk[stk_top--];
        }
        if (stk_top > 0) tree_r[mono_stk[stk_top]] = i;
        if (last > 0) tree_l[i] = last;
        mono_stk[++stk_top] = i;
    }
    return mono_stk[1]; // 栈底元素即为整棵树的根节点
}
```

---

### 3.5 无旋 Treap (FHQ Treap - 平衡树)

FHQ Treap（分裂合并式平衡树）是由范浩强设计的一种非旋转式平衡树。它通过**分裂 (Split)** 与**合并 (Merge)** 操作来维持树的自平衡。由于所有操作都不需要复杂的旋转逻辑，仅通过一维静态平行数组即可完成编写。

```cpp
#include <random>

// 平行数组维护平衡树节点信息
int tr_l[N], tr_r[N], tr_val[N], tr_key[N], tr_size[N], treap_cnt;

std::mt19937 rnd(13331); // 随机数生成器，用于堆的随机权重分配

void pushup_size(int u) {
    tr_size[u] = tr_size[tr_l[u]] + tr_size[tr_r[u]] + 1;
}

int create_treap_node(int v) {
    treap_cnt++;
    tr_val[treap_cnt] = v;
    tr_key[treap_cnt] = rnd();
    tr_size[treap_cnt] = 1;
    tr_l[treap_cnt] = tr_r[treap_cnt] = 0;
    return treap_cnt;
}

// 核心操作 1：分裂
// 将以 u 为根的树，按数值 v 分裂为两棵树 x 和 y，其中 x 中的值都 <= v，y 中的值都 > v
void split(int u, int v, int& x, int& y) {
    if (!u) {
        x = y = 0;
        return;
    }
    if (tr_val[u] <= v) {
        x = u;
        split(tr_r[u], v, tr_r[u], y);
        pushup_size(x);
    } else {
        y = u;
        split(tr_l[u], v, x, tr_l[u]);
        pushup_size(y);
    }
}

// 核心操作 2：合并
// 合并树 x 和树 y，返回合并后的根，要求树 x 中的最大值小于等于树 y 中的最小值
int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr_key[x] < tr_key[y]) { // 依据优先级合并，维护堆性质
        tr_r[x] = merge(tr_r[x], y);
        pushup_size(x);
        return x;
    } else {
        tr_l[y] = merge(x, tr_l[y]);
        pushup_size(y);
        return y;
    }
}
```

---

## 4. 常见图存储与二分图判定

我们使用静态链式前向星对图进行存储。

### 4.1 链式前向星定义与加边
```cpp
const int M = 200010;
int head[N], to_node[M], next_edge[M], edge_cnt;

void init_graph() {
    std::fill(head, head + N, -1);
    edge_cnt = 0;
}

void add_edge(int u, int v) {
    to_node[edge_cnt] = v;
    next_edge[edge_cnt] = head[u];
    head[u] = edge_cnt++;
}
```

---

### 4.2 偶图 (二分图) 的 DFS 判定（双色着色法）

*   **定理**：一个无向图是二分图的充要条件是其**不存在奇环**（环中边数为奇数）。
*   我们可以通过 DFS 尝试使用两色（1和2）为图中所有节点着色。如果染色过程中发现相邻两节点颜色相同，则说明图含有奇环，不是二分图。

```cpp
int color[N]; // 初始为 0，1和2为两种不同颜色

bool dfs_color(int u, int c) {
    color[u] = c;
    for (int i = head[u]; i != -1; i = next_edge[i]) {
        int v = to_node[i];
        if (!color[v]) {
            if (!dfs_color(v, 3 - c)) return false; // 3 - c 能在 1 和 2 之间切换
        } else if (color[v] == c) {
            return false; // 颜色冲突
        }
    }
    return true;
}

bool is_bipartite(int n) {
    std::fill(color, color + n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (!color[i]) {
            if (!dfs_color(i, 1)) return false;
        }
    }
    return true;
}
```

---

## 5. 哈希表 (Hash Table)

当需要存储和查询庞大的稀疏集合时，哈希表是必不可少的。

### 5.1 数值哈希函数与拉链法解决冲突
拉链法的底层逻辑与链式前向星相同。

```cpp
const int HASH_MOD = 99997; // 哈希桶大小，通常选用一个较大的质数
int h_head[HASH_MOD], h_val[N], h_next[N], hash_cnt;

void init_hash_table() {
    std::fill(h_head, h_head + HASH_MOD, -1);
    hash_cnt = 0;
}

// 插入哈希值
void hash_insert(int key) {
    int hash_pos = (key % HASH_MOD + HASH_MOD) % HASH_MOD; // 转换负数为正哈希位置
    h_val[hash_cnt] = key;
    h_next[hash_cnt] = h_head[hash_pos];
    h_head[hash_pos] = hash_cnt++;
}

// 查询是否存在
bool hash_find(int key) {
    int hash_pos = (key % HASH_MOD + HASH_MOD) % HASH_MOD;
    for (int i = h_head[hash_pos]; i != -1; i = h_next[i]) {
        if (h_val[i] == key) return true;
    }
    return false;
}
```

---

### 5.2 字符串哈希 (String Hash - 滚动哈希)
通过对字符串进行多项式编码，将任意长度的字符串转换为一个 `unsigned long long` 类型的整数。因为 `unsigned long long` 溢出时会自动对 $2^{64}$ 进行取模，这天然起到了哈希冲突模数的作用。

#### 1. 滚动哈希公式
设基数为 $P = 131$ 或 $P = 13331$，字符串 $S$ 的前缀哈希 $h[i]$ 定义为：
$$h[i] = h[i-1] \cdot P + S[i]$$
区间 $[L, R]$ 的子串哈希值可以在 $O(1)$ 时间内快速计算：
$$\text{Hash}(S[L \dots R]) = h[R] - h[L-1] \cdot P^{R-L+1}$$

#### 2. C++11 实现
```cpp
using ULL = unsigned long long;
const int P_BASE = 131;

ULL h_arr[N], p_pow[N];

void init_string_hash(const char* s, int n) {
    p_pow[0] = 1;
    h_arr[0] = 0;
    for (int i = 1; i <= n; ++i) {
        p_pow[i] = p_pow[i - 1] * P_BASE;
        h_arr[i] = h_arr[i - 1] * P_BASE + s[i - 1];
    }
}

// 获取子区间 [l, r] 对应的子串哈希值（1-Based Index）
ULL get_substring_hash(int l, int r) {
    return h_arr[r] - h_arr[l - 1] * p_pow[r - l + 1];
}
```

---

## 6. 综合练习题与解析

### 练习题 1：区间动态加减与求和（静态线段树应用）
**题目描述**：
给定一个长度为 $N$ 的初始整数序列，有 $M$ 次操作。操作有两种类型：
1. `1 L R C`：将区间 $[L, R]$ 里的每个数都加上 $C$。
2. `2 L R`：查询并输出区间 $[L, R]$ 的元素总和。
$1 \le N, M \le 10^5$，保证计算结果不超过 `long long` 的表示范围。

#### C++11 实现与解析
```cpp
#include <iostream>
#include <cstdio>
#include <algorithm>

using LL = long long;
constexpr int MAX_N = 100010;

LL sum_tr[MAX_N * 4], lazy[MAX_N * 4];
int raw_arr[MAX_N];

void pushup(int u) {
    sum_tr[u] = sum_tr[u << 1] + sum_tr[u << 1 | 1];
}

void pushdown(int u, int l, int r) {
    if (lazy[u]) {
        int mid = l + (r - l) / 2;
        
        lazy[u << 1] += lazy[u];
        sum_tr[u << 1] += lazy[u] * (mid - l + 1);
        
        lazy[u << 1 | 1] += lazy[u];
        sum_tr[u << 1 | 1] += lazy[u] * (r - mid);
        
        lazy[u] = 0;
    }
}

void build(int u, int l, int r) {
    lazy[u] = 0;
    if (l == r) {
        sum_tr[u] = raw_arr[l];
        return;
    }
    int mid = l + (r - l) / 2;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int L, int R, LL val) {
    if (L <= l && r <= R) {
        sum_tr[u] += val * (r - l + 1);
        lazy[u] += val;
        return;
    }
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    if (L <= mid) update(u << 1, l, mid, L, R, val);
    if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, val);
    pushup(u);
}

LL query(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum_tr[u];
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    LL res = 0;
    if (L <= mid) res += query(u << 1, l, mid, L, R);
    if (R > mid) res += query(u << 1 | 1, mid + 1, r, L, R);
    return res;
}

int main() {
    // 假设输入数据：N=5, M=3
    int n = 5, m = 3;
    int test_input[] = {0, 1, 2, 3, 4, 5}; // 1-Based Index
    for (int i = 1; i <= n; ++i) raw_arr[i] = test_input[i];
    
    build(1, 1, n);
    
    // 操作 1：区间 [1, 3] 加上 2
    update(1, 1, n, 1, 3, 2);
    
    // 操作 2：区间 [2, 5] 求和
    // 原始序列加上修改后为：[3, 4, 5, 4, 5]，和为 18
    std::cout << "Sum of range [2, 5]: " << query(1, 1, n, 2, 5) << "\n"; // 输出 18
    return 0;
}
```
**解题思路**：
线段树是解决区间问题最强大的工具之一。其通过将区间拆分为 $\log n$ 个局部线段节点进行维护。本题使用经典的静态 4 倍空间大小的数组进行树结构存储。
1. `pushdown` 用于实现懒标记的下传：当我们在某个大区间直接打上修改标记并计算完和后，无需立即递归修改子叶子节点（该操作延迟到后续需要访问该子树时再通过 `pushdown` 执行），从而使单次修改的时间复杂度从 $O(n)$ 降到了 $O(\log n)$。
2. 整个算法结构不使用任何动态指针，纯一维数组操作，最大程度降低了寻址延迟和运行期不必要的函数开销。

---

### 练习题 2：树状数组维护差分实现区间加、单点值查询
**题目描述**：
维护一个数列，需要支持以下两种操作：
1. `1 L R C`：将区间 $[L, R]$ 里的每个数都加上 $C$。
2. `2 X`：单点查询原序列第 $X$ 个位置的最新数值。
数据范围：$N, M \le 10^5$。

#### C++11 实现与解析
```cpp
#include <iostream>

constexpr int MAX_BIT = 100010;
int bit_tr[MAX_BIT];
int n_size;

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

// 单点在差分数组上做加法
void bit_add(int x, int c) {
    for (int i = x; i <= n_size; i += l_bit(i)) bit_tr[i] += c;
}

// 查询差分数组前缀和，即为单点值
int bit_query(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= l_bit(i)) sum += bit_tr[i];
    return sum;
}

int main() {
    n_size = 5;
    int initial_arr[] = {0, 10, 20, 30, 40, 50}; // 1-Based Index
    
    // 初始化差分树状数组
    for (int i = 1; i <= n_size; ++i) {
        int diff = initial_arr[i] - initial_arr[i - 1];
        bit_add(i, diff);
    }
    
    // 操作 1：将区间 [2, 4] 加上 5
    // 差分修改：bit_add(L, c), bit_add(R + 1, -c)
    bit_add(2, 5);
    bit_add(4 + 1, -5);
    
    // 操作 2：查询第 3 个位置的值
    // 原始 30 -> 加上 5 后为 35
    std::cout << "Value at position 3: " << bit_query(3) << "\n"; // 输出 35
    return 0;
}
```
**解题思路**：
本题如果直接使用线段树，虽然能实现，但代码量大且内存常数开销较大。
由于本题只需要**单点值查询**与**区间更新**，我们可以将**差分思想**与**树状数组**巧妙结合：
1. 设原序列为 $A$，建立差分数组 $D[i] = A[i] - A[i-1]$。则有：
   $$A[x] = \sum\_{j=1}^{x} D[j]$$
   也就是说，原序列的单点值，其实就是差分数组的前缀和。
2. 我们用树状数组维护差分数组 $D$。
3. 当需要在区间 $[L, R]$ 统一加上 $C$ 时，等价于对差分数组执行：$D[L] \leftarrow D[L] + C, D[R+1] \leftarrow D[R+1] - C$。我们在树状数组上执行两次单点加操作即可。
4. 当需要查询第 $X$ 位的值时，只需查询树状数组前缀和 `bit_query(X)`，时间复杂度仅为 $O(\log n)$。整个程序非常简洁，易于在考场上快速编写和调试。

C++11 高级数据结构（静态数组模拟版）讲义

在解决算法竞赛（如 CSP-S、NOI）中的高难度问题时，使用指针与结构体动态分配内存常面临执行效率低（因频繁申请堆内存）及容易出现内存泄露或段错误等风险。

本讲义严格基于 C++11 标准，所有高级数据结构全部采用静态一维/多维平行数组进行模拟。这样不仅能将运行速度提升至接近硬件极限，而且代码结构极为规整，便于调试与维护。

1. 线性结构

1.1 双端栈 (Double-ended Stack)

双端栈是指两个栈共享同一个一维数组空间。一个栈顶设在数组的左端点（向右增长），另一个栈顶设在数组的右端点（向左增长）。

1. 结构设计与边界

设数组大小为 $N$，左栈顶为 top1，右栈顶为 top2： * 初始状态：top1 = -1, top2 = N * 栈满条件：top1 + 1 == top2

2. C++11 实现

constexpr int N = 100010;
int destk[N];
int top1 = -1, top2 = N;

void push1(int x) {
    if (top1 + 1 < top2) destk[++top1] = x;
}

void push2(int x) {
    if (top1 + 1 < top2) destk[--top2] = x;
}

void pop1() {
    if (top1 >= 0) top1--;
}

void pop2() {
    if (top2 < N) top2++;
}

1.2 双端队列 (Double-ended Queue / Deque)

双端队列允许在队列的两端进行插入与删除。我们利用一个足够大的静态数组与两个指针 hh（头指针）和 tt（尾指针）来模拟。

int deq[N * 2]; // 空间开双倍，防止向左或向右单向溢出
int hh = N, tt = N - 1; // 初始位置设在数组中心

void push_back(int x) {
    deq[++tt] = x;
}

void push_front(int x) {
    deq[--hh] = x;
}

void pop_back() {
    if (hh <= tt) tt--;
}

void pop_front() {
    if (hh <= tt) hh++;
}

1.3 单调队列 (Monotonic Queue)

单调队列是一种维护其内部元素具有单调性（递增或递减）的双端队列。其最经典的应用是解决滑动窗口最值问题。

1. 算法复杂度证明

设序列长度为 $n$，滑动窗口大小为 $k$： * 定理：单调队列求解滑动窗口最值的时间复杂度为 $O(n)$。 * 证明：在整个处理流程中，序列中的每个元素 $i$ 最多只会执行一次入队（通过 tt++）和至多一次出队（通过 hh++ 或 tt--）。因为入队和出队的总次数均不超过 $n$，所以总时间复杂度在均摊意义下为 $O(n)$。

2. C++11 实现：滑动窗口最小值

int a[N]; // 原序列
int q[N]; // 存储原序列的下标而非数值
int hh = 0, tt = -1;

void sliding_window_min(int n, int k) {
    hh = 0, tt = -1;
    for (int i = 0; i < n; ++i) {
        // 1. 判断队头元素是否滑出窗口
        if (hh <= tt && q[hh] < i - k + 1) hh++;

        // 2. 保持队列单调递增：若新加入的值 a[i] 小于等于队尾对应的元素，则将队尾弹出
        while (hh <= tt && a[q[tt]] >= a[i]) tt--;

        // 3. 将当前元素的下标压入队列
        q[++tt] = i;

        // 4. 当窗口形成后，队头即为当前窗口的最小值
        if (i >= k - 1) {
            std::cout << a[q[hh]] << " ";
        }
    }
}

1.4 静态二叉堆（优先队列）

堆是一个完全二叉树。我们采用一维数组进行物理映射存储，索引从 $1$ 开始： * 若节点索引为 $u$，则左孩子为 $2u$，右孩子为 $2u+1$，双亲为 $\lfloor u/2 \rfloor$。

C++11 实现（小顶堆）

int heap[N], heap_size = 0;

void down(int u) {
    int t = u;
    if (u * 2 <= heap_size && heap[u * 2] < heap[t]) t = u * 2;
    if (u * 2 + 1 <= heap_size && heap[u * 2 + 1] < heap[t]) t = u * 2 + 1;
    if (u != t) {
        std::swap(heap[u], heap[t]);
        down(t);
    }
}

void up(int u) {
    while (u / 2 && heap[u / 2] > heap[u]) {
        std::swap(heap[u / 2], heap[u]);
        u /= 2;
    }
}

void push(int x) {
    heap[++heap_size] = x;
    up(heap_size);
}

void pop() {
    heap[1] = heap[heap_size--];
    down(1);
}

int top() {
    return heap[1];
}

1.5 ST 表 (Sparse Table)

ST 表用于解决区间最值查询（RMQ）问题。其基于倍增和动态规划思想。

1. 状态转移

$f[i][j]$ 表示以 $i$ 为起点，长度为 $2^j$ 的区间内的最值。由于区间可以重叠且最值操作满足幂等性（即 $\max(x, x) = x$），查询区间 $[L, R]$ 时，设其跨度长度的对数为 $k = \lfloor \log_2(R-L+1) \rfloor$，则有： $$\text{RMQ}(L, R) = \max(f[L][k], f[R - 2^k + 1][k])$$

2. C++11 预处理与查询

#include <algorithm>

int f[N][20];
int lg[N];

void init_st_table(int arr[], int n) {
    lg[1] = 0;
    for (int i = 2; i <= n; ++i) lg[i] = lg[i / 2] + 1;

    for (int i = 1; i <= n; ++i) f[i][0] = arr[i];

    for (int j = 1; j < 20; ++j) {
        for (int i = 1; i + (1 << j) - 1 <= n; ++i) {
            f[i][j] = std::max(f[i][j - 1], f[i + (1 << (j - 1))][j - 1]);
        }
    }
}

int query_st(int l, int r) {
    int k = lg[r - l + 1];
    return std::max(f[l][k], f[r - (1 << k) + 1][k]);
}

2. 集合与森林

2.1 并查集 (Disjoint Set Union, DSU)

并查集用于处理集合的合并与查询。

1. 路径压缩优化复杂度

在并查集中，如果不进行任何优化，退化的树形结构会导致单次查询的时间复杂度退化为 $O(n)$。通过路径压缩（Path Compression），在每次执行查找根节点操作时，将路径上所有遇到的节点直接挂载到根节点上。

定理：结合路径压缩与按秩合并（或大小合并）的并查集，单次操作的均摊时间复杂度为 $O(\alpha(n))$，其中 $\alpha$ 为反阿克曼函数，是一个增长极其缓慢的函数（对所有实际物理数值，$\alpha(n) \le 4$）。

2. C++11 实现

int p[N]; // 记录每个节点的双亲

void init_dsu(int n) {
    for (int i = 1; i <= n; ++i) p[i] = i;
}

// 包含路径压缩的查找根节点函数
int find(int x) {
    if (p[x] != x) p[x] = find(p[x]); // 递归压缩路径
    return p[x];
}

// 合并操作
void merge(int x, int y) {
    int root_x = find(x);
    int root_y = find(y);
    if (root_x != root_y) {
        p[root_x] = root_y;
    }
}

2.2 树的孩子兄弟表示法

对于一般的多叉树，如果不通过结构体指针表示，可以通过静态一维数组模拟： * first_child[u]：存储节点 $u$ 的第一个长子。 * next_sibling[u]：存储节点 $u$ 紧邻的下一个右侧兄弟节点。

int first_child[N], next_sibling[N];

void init_tree_nodes(int n) {
    std::fill(first_child, first_child + n + 1, -1);
    std::fill(next_sibling, next_sibling + n + 1, -1);
}

// 给节点 u 添加子节点 v
void add_child(int u, int v) {
    if (first_child[u] == -1) {
        first_child[u] = v;
    } else {
        int curr = first_child[u];
        while (next_sibling[curr] != -1) {
            curr = next_sibling[curr];
        }
        next_sibling[curr] = v;
    }
}

3. 特殊树结构

3.1 树状数组 (Fenwick Tree / Binary Indexed Tree)

树状数组常用于高效计算区间的动态单点修改与前缀和查询。

1. `lowbit` 机制证明

设一个正整数 $x$ 的二进制表示为 $x = \text{bin_arr} \cdot 2^k$。其 lowbit 定义为取出 $x$ 二进制表示中最低位的 $1$ 及其后面的 $0$： $$\text{lowbit}(x) = x \ \& \ (-x)$$

证明：在计算机中，负数以补码形式存储。设 $x$ 的二进制最低位 1 出现在第 $k$ 位，则： $$x = \dots 1 \underbrace{0 \dots 0}_{k \text{ 个 } 0}$$ 其反码 $\sim x$ 将该最低位的 1 变为 0，后面的 0 均变为 1。其补码 $-x = \sim x + 1$ 会导致最低位右侧的所有 1 产生进位，从而使原第 $k$ 位重新变回 1，且其右侧所有位重置为 0。对 $x$ 与 $-x$ 进行按位与 & 运算后，第 $k$ 位左侧因为按位反转全部归 0，右侧也为 0，只有第 $k$ 位保持为 1。因此，结果恰好为 $2^k$。

2. C++11 实现

int tr[N];
int limit_n;

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

// 单点增加 c
void add(int x, int c) {
    for (int i = x; i <= limit_n; i += lowbit(i)) tr[i] += c;
}

// 查询前缀和 [1, x]
int query(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= lowbit(i)) sum += tr[i];
    return sum;
}

3.2 线段树 (Segment Tree)

线段树用于维护区间上的合并信息，支持区间修改与区间查询。通过懒标记 (Lazy Tag)，可以将区间更新的均摊时间复杂度降至 $O(\log n)$。

// 静态线段树：空间需要开辟原序列大小的 4 倍
int sum_tr[N * 4], lazy[N * 4];

void pushup(int u) {
    sum_tr[u] = sum_tr[u << 1] + sum_tr[u << 1 | 1];
}

void pushdown(int u, int l, int r) {
    if (lazy[u]) {
        int mid = l + (r - l) / 2;
        // 分发懒标记
        lazy[u << 1] += lazy[u];
        sum_tr[u << 1] += lazy[u] * (mid - l + 1);

        lazy[u << 1 | 1] += lazy[u];
        sum_tr[u << 1 | 1] += lazy[u] * (r - mid);

        lazy[u] = 0; // 清除当前标记
    }
}

// 区间修改：[L, R] 统一加上 val
void update(int u, int l, int r, int L, int R, int val) {
    if (L <= l && r <= R) {
        sum_tr[u] += val * (r - l + 1);
        lazy[u] += val;
        return;
    }
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    if (L <= mid) update(u << 1, l, mid, L, R, val);
    if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, val);
    pushup(u);
}

// 区间查询：求 [L, R] 内的元素和
int query(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum_tr[u];
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    int res = 0;
    if (L <= mid) res += query(u << 1, l, mid, L, R);
    if (R > mid) res += query(u << 1 | 1, mid + 1, r, L, R);
    return res;
}

3.3 字典树 (Trie)

字典树又称前缀树，用于高效存储和检索字符串集合。

int son[N][26]; // 26个英文字母分支
int cnt[N];     // 记录以当前节点结尾的单词数量
int trie_idx;   // 静态分配节点

void trie_insert(const char* str) {
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - 'a';
        if (!son[p][u]) son[p][u] = ++trie_idx;
        p = son[p][u];
    }
    cnt[p]++;
}

int trie_query(const char* str) {
    int p = 0;
    for (int i = 0; str[i]; ++i) {
        int u = str[i] - 'a';
        if (!son[p][u]) return 0;
        p = son[p][u];
    }
    return cnt[p];
}

3.4 笛卡尔树 (Cartesian Tree)

笛卡尔树是一棵二叉树，每个节点存储一个二元组 $(key, val)$： 1. 其关于键值 $key$ 满足二叉搜索树的性质。 2. 其关于权值 $val$ 满足堆的性质。

当 $key$ 递增时（如一维数组的索引），笛卡尔树可以在 $O(n)$ 线性时间内利用单调栈构建完成。

C++11 实现

int tree_l[N], tree_r[N], val[N];
int mono_stk[N], stk_top;

// 构建笛卡尔树并返回根节点
int build_cartesian_tree(int n) {
    stk_top = 0;
    std::fill(tree_l, tree_l + n + 1, 0);
    std::fill(tree_r, tree_r + n + 1, 0);

    for (int i = 1; i <= n; ++i) {
        int last = 0;
        // 维持栈内元素权值单调递增（小顶堆）
        while (stk_top > 0 && val[mono_stk[stk_top]] > val[i]) {
            last = mono_stk[stk_top--];
        }
        if (stk_top > 0) tree_r[mono_stk[stk_top]] = i;
        if (last > 0) tree_l[i] = last;
        mono_stk[++stk_top] = i;
    }
    return mono_stk[1]; // 栈底元素即为整棵树的根节点
}

3.5 无旋 Treap (FHQ Treap - 平衡树)

FHQ Treap（分裂合并式平衡树）是由范浩强设计的一种非旋转式平衡树。它通过分裂 (Split) 与合并 (Merge) 操作来维持树的自平衡。由于所有操作都不需要复杂的旋转逻辑，仅通过一维静态平行数组即可完成编写。

#include <random>

// 平行数组维护平衡树节点信息
int tr_l[N], tr_r[N], tr_val[N], tr_key[N], tr_size[N], treap_cnt;

std::mt19937 rnd(13331); // 随机数生成器，用于堆的随机权重分配

void pushup_size(int u) {
    tr_size[u] = tr_size[tr_l[u]] + tr_size[tr_r[u]] + 1;
}

int create_treap_node(int v) {
    treap_cnt++;
    tr_val[treap_cnt] = v;
    tr_key[treap_cnt] = rnd();
    tr_size[treap_cnt] = 1;
    tr_l[treap_cnt] = tr_r[treap_cnt] = 0;
    return treap_cnt;
}

// 核心操作 1：分裂
// 将以 u 为根的树，按数值 v 分裂为两棵树 x 和 y，其中 x 中的值都 <= v，y 中的值都 > v
void split(int u, int v, int& x, int& y) {
    if (!u) {
        x = y = 0;
        return;
    }
    if (tr_val[u] <= v) {
        x = u;
        split(tr_r[u], v, tr_r[u], y);
        pushup_size(x);
    } else {
        y = u;
        split(tr_l[u], v, x, tr_l[u]);
        pushup_size(y);
    }
}

// 核心操作 2：合并
// 合并树 x 和树 y，返回合并后的根，要求树 x 中的最大值小于等于树 y 中的最小值
int merge(int x, int y) {
    if (!x || !y) return x + y;
    if (tr_key[x] < tr_key[y]) { // 依据优先级合并，维护堆性质
        tr_r[x] = merge(tr_r[x], y);
        pushup_size(x);
        return x;
    } else {
        tr_l[y] = merge(x, tr_l[y]);
        pushup_size(y);
        return y;
    }
}

4. 常见图存储与二分图判定

我们使用静态链式前向星对图进行存储。

4.1 链式前向星定义与加边

const int M = 200010;
int head[N], to_node[M], next_edge[M], edge_cnt;

void init_graph() {
    std::fill(head, head + N, -1);
    edge_cnt = 0;
}

void add_edge(int u, int v) {
    to_node[edge_cnt] = v;
    next_edge[edge_cnt] = head[u];
    head[u] = edge_cnt++;
}

4.2 偶图 (二分图) 的 DFS 判定（双色着色法）

定理：一个无向图是二分图的充要条件是其不存在奇环（环中边数为奇数）。
我们可以通过 DFS 尝试使用两色（1和2）为图中所有节点着色。如果染色过程中发现相邻两节点颜色相同，则说明图含有奇环，不是二分图。

int color[N]; // 初始为 0，1和2为两种不同颜色

bool dfs_color(int u, int c) {
    color[u] = c;
    for (int i = head[u]; i != -1; i = next_edge[i]) {
        int v = to_node[i];
        if (!color[v]) {
            if (!dfs_color(v, 3 - c)) return false; // 3 - c 能在 1 和 2 之间切换
        } else if (color[v] == c) {
            return false; // 颜色冲突
        }
    }
    return true;
}

bool is_bipartite(int n) {
    std::fill(color, color + n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        if (!color[i]) {
            if (!dfs_color(i, 1)) return false;
        }
    }
    return true;
}

5. 哈希表 (Hash Table)

当需要存储和查询庞大的稀疏集合时，哈希表是必不可少的。

5.1 数值哈希函数与拉链法解决冲突

拉链法的底层逻辑与链式前向星相同。

const int HASH_MOD = 99997; // 哈希桶大小，通常选用一个较大的质数
int h_head[HASH_MOD], h_val[N], h_next[N], hash_cnt;

void init_hash_table() {
    std::fill(h_head, h_head + HASH_MOD, -1);
    hash_cnt = 0;
}

// 插入哈希值
void hash_insert(int key) {
    int hash_pos = (key % HASH_MOD + HASH_MOD) % HASH_MOD; // 转换负数为正哈希位置
    h_val[hash_cnt] = key;
    h_next[hash_cnt] = h_head[hash_pos];
    h_head[hash_pos] = hash_cnt++;
}

// 查询是否存在
bool hash_find(int key) {
    int hash_pos = (key % HASH_MOD + HASH_MOD) % HASH_MOD;
    for (int i = h_head[hash_pos]; i != -1; i = h_next[i]) {
        if (h_val[i] == key) return true;
    }
    return false;
}

5.2 字符串哈希 (String Hash - 滚动哈希)

通过对字符串进行多项式编码，将任意长度的字符串转换为一个 unsigned long long 类型的整数。因为 unsigned long long 溢出时会自动对 $2^{64}$ 进行取模，这天然起到了哈希冲突模数的作用。

1. 滚动哈希公式

设基数为 $P = 131$ 或 $P = 13331$，字符串 $S$ 的前缀哈希 $h[i]$ 定义为： $$h[i] = h[i-1] \cdot P + S[i]$$ 区间 $[L, R]$ 的子串哈希值可以在 $O(1)$ 时间内快速计算： $$\text{Hash}(S[L \dots R]) = h[R] - h[L-1] \cdot P^{R-L+1}$$

2. C++11 实现

using ULL = unsigned long long;
const int P_BASE = 131;

ULL h_arr[N], p_pow[N];

void init_string_hash(const char* s, int n) {
    p_pow[0] = 1;
    h_arr[0] = 0;
    for (int i = 1; i <= n; ++i) {
        p_pow[i] = p_pow[i - 1] * P_BASE;
        h_arr[i] = h_arr[i - 1] * P_BASE + s[i - 1];
    }
}

// 获取子区间 [l, r] 对应的子串哈希值（1-Based Index）
ULL get_substring_hash(int l, int r) {
    return h_arr[r] - h_arr[l - 1] * p_pow[r - l + 1];
}

6. 综合练习题与解析

练习题 1：区间动态加减与求和（静态线段树应用）

题目描述：给定一个长度为 $N$ 的初始整数序列，有 $M$ 次操作。操作有两种类型： 1. 1 L R C：将区间 $[L, R]$ 里的每个数都加上 $C$。 2. 2 L R：查询并输出区间 $[L, R]$ 的元素总和。 $1 \le N, M \le 10^5$，保证计算结果不超过 long long 的表示范围。

C++11 实现与解析

#include <iostream>
#include <cstdio>
#include <algorithm>

using LL = long long;
constexpr int MAX_N = 100010;

LL sum_tr[MAX_N * 4], lazy[MAX_N * 4];
int raw_arr[MAX_N];

void pushup(int u) {
    sum_tr[u] = sum_tr[u << 1] + sum_tr[u << 1 | 1];
}

void pushdown(int u, int l, int r) {
    if (lazy[u]) {
        int mid = l + (r - l) / 2;

        lazy[u << 1] += lazy[u];
        sum_tr[u << 1] += lazy[u] * (mid - l + 1);

        lazy[u << 1 | 1] += lazy[u];
        sum_tr[u << 1 | 1] += lazy[u] * (r - mid);

        lazy[u] = 0;
    }
}

void build(int u, int l, int r) {
    lazy[u] = 0;
    if (l == r) {
        sum_tr[u] = raw_arr[l];
        return;
    }
    int mid = l + (r - l) / 2;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
    pushup(u);
}

void update(int u, int l, int r, int L, int R, LL val) {
    if (L <= l && r <= R) {
        sum_tr[u] += val * (r - l + 1);
        lazy[u] += val;
        return;
    }
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    if (L <= mid) update(u << 1, l, mid, L, R, val);
    if (R > mid) update(u << 1 | 1, mid + 1, r, L, R, val);
    pushup(u);
}

LL query(int u, int l, int r, int L, int R) {
    if (L <= l && r <= R) return sum_tr[u];
    pushdown(u, l, r);
    int mid = l + (r - l) / 2;
    LL res = 0;
    if (L <= mid) res += query(u << 1, l, mid, L, R);
    if (R > mid) res += query(u << 1 | 1, mid + 1, r, L, R);
    return res;
}

int main() {
    // 假设输入数据：N=5, M=3
    int n = 5, m = 3;
    int test_input[] = {0, 1, 2, 3, 4, 5}; // 1-Based Index
    for (int i = 1; i <= n; ++i) raw_arr[i] = test_input[i];

    build(1, 1, n);

    // 操作 1：区间 [1, 3] 加上 2
    update(1, 1, n, 1, 3, 2);

    // 操作 2：区间 [2, 5] 求和
    // 原始序列加上修改后为：[3, 4, 5, 4, 5]，和为 18
    std::cout << "Sum of range [2, 5]: " << query(1, 1, n, 2, 5) << "\n"; // 输出 18
    return 0;
}

解题思路：线段树是解决区间问题最强大的工具之一。其通过将区间拆分为 $\log n$ 个局部线段节点进行维护。本题使用经典的静态 4 倍空间大小的数组进行树结构存储。 1. pushdown 用于实现懒标记的下传：当我们在某个大区间直接打上修改标记并计算完和后，无需立即递归修改子叶子节点（该操作延迟到后续需要访问该子树时再通过 pushdown 执行），从而使单次修改的时间复杂度从 $O(n)$ 降到了 $O(\log n)$。 2. 整个算法结构不使用任何动态指针，纯一维数组操作，最大程度降低了寻址延迟和运行期不必要的函数开销。

练习题 2：树状数组维护差分实现区间加、单点值查询

题目描述：维护一个数列，需要支持以下两种操作： 1. 1 L R C：将区间 $[L, R]$ 里的每个数都加上 $C$。 2. 2 X：单点查询原序列第 $X$ 个位置的最新数值。数据范围：$N, M \le 10^5$。

C++11 实现与解析

#include <iostream>

constexpr int MAX_BIT = 100010;
int bit_tr[MAX_BIT];
int n_size;

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

// 单点在差分数组上做加法
void bit_add(int x, int c) {
    for (int i = x; i <= n_size; i += l_bit(i)) bit_tr[i] += c;
}

// 查询差分数组前缀和，即为单点值
int bit_query(int x) {
    int sum = 0;
    for (int i = x; i > 0; i -= l_bit(i)) sum += bit_tr[i];
    return sum;
}

int main() {
    n_size = 5;
    int initial_arr[] = {0, 10, 20, 30, 40, 50}; // 1-Based Index

    // 初始化差分树状数组
    for (int i = 1; i <= n_size; ++i) {
        int diff = initial_arr[i] - initial_arr[i - 1];
        bit_add(i, diff);
    }

    // 操作 1：将区间 [2, 4] 加上 5
    // 差分修改：bit_add(L, c), bit_add(R + 1, -c)
    bit_add(2, 5);
    bit_add(4 + 1, -5);

    // 操作 2：查询第 3 个位置的值
    // 原始 30 -> 加上 5 后为 35
    std::cout << "Value at position 3: " << bit_query(3) << "\n"; // 输出 35
    return 0;
}

解题思路：本题如果直接使用线段树，虽然能实现，但代码量大且内存常数开销较大。由于本题只需要单点值查询与区间更新，我们可以将差分思想与树状数组巧妙结合： 1. 设原序列为 $A$，建立差分数组 $D[i] = A[i] - A[i-1]$。则有： $$A[x] = \sum_{j=1}^{x} D[j]$$ 也就是说，原序列的单点值，其实就是差分数组的前缀和。 2. 我们用树状数组维护差分数组 $D$。 3. 当需要在区间 $[L, R]$ 统一加上 $C$ 时，等价于对差分数组执行：$D[L] \leftarrow D[L] + C, D[R+1] \leftarrow D[R+1] - C$。我们在树状数组上执行两次单点加操作即可。 4. 当需要查询第 $X$ 位的值时，只需查询树状数组前缀和 bit_query(X)，时间复杂度仅为 $O(\log n)$。整个程序非常简洁，易于在考场上快速编写和调试。

—— 本文来自火龙信奥（义乌睿码科技）：义乌青少年信息学奥赛与编程教育平台，专注 CSP-J/S、NOIP、GESP 竞赛培训，线上线下融合教学，助力编程升学。网址：hlcoding.com

提高组大纲2.2.3数据结构

C++11 高级数据结构（静态数组模拟版）讲义

1. 线性结构

1.1 双端栈 (Double-ended Stack)

1. 结构设计与边界

2. C++11 实现

1.2 双端队列 (Double-ended Queue / Deque)

1.3 单调队列 (Monotonic Queue)

1. 算法复杂度证明

2. C++11 实现：滑动窗口最小值

1.4 静态二叉堆（优先队列）

C++11 实现（小顶堆）

1.5 ST 表 (Sparse Table)

1. 状态转移

2. C++11 预处理与查询

2. 集合与森林

2.1 并查集 (Disjoint Set Union, DSU)

1. 路径压缩优化复杂度

2. C++11 实现

2.2 树的孩子兄弟表示法

3. 特殊树结构

3.1 树状数组 (Fenwick Tree / Binary Indexed Tree)

1. lowbit 机制证明

2. C++11 实现

3.2 线段树 (Segment Tree)

3.3 字典树 (Trie)

3.4 笛卡尔树 (Cartesian Tree)

C++11 实现

3.5 无旋 Treap (FHQ Treap - 平衡树)

4. 常见图存储与二分图判定

4.1 链式前向星定义与加边

4.2 偶图 (二分图) 的 DFS 判定（双色着色法）

5. 哈希表 (Hash Table)

5.1 数值哈希函数与拉链法解决冲突

5.2 字符串哈希 (String Hash - 滚动哈希)

1. 滚动哈希公式

2. C++11 实现

6. 综合练习题与解析

练习题 1：区间动态加减与求和（静态线段树应用）

C++11 实现与解析

练习题 2：树状数组维护差分实现区间加、单点值查询

C++11 实现与解析

1. `lowbit` 机制证明