NeFut Logo NeFut
EN 管理员登录

动态区间第 K 大问题的高效解决方案：树状数组与权值线段树的结合

发布于：2026-05-27 09:17 最后更新：2026-06-10 09:27
#C++ #Tutorial

核心逻辑与数学原理

在 7.3 节中，我们利用可持久化权值线段树（主席树）的前缀和差分特性，在 $O(\text{log} N)$ 复杂度内完美解决了静态区间第 $K$ 大问题。然而，一旦题目引入动态单点修改（如：将原序列第 $i$ 个数修改为 $X$），静态主席树的前缀和链条将被彻底打断。因为修改序列中的一个数，会导致其后所有的前缀版本（$Root[i]$ 至 $Root[N]$）全部失效，若强行重构，单次修改的时间复杂度将退化为 $O(N \text{log} N)$。

树状数组套权值线段树（Fenwick Tree serving Dynamically Allocated Value Segment Trees），即所谓带修改的主席树，是解决这一动态高维检索问题的省选级破局大招。

1. 经典动态前缀和的维数退化

面对动态前缀和修改，最成熟的底盘算法是树状数组（Lowbit 优化）。树状数组将大小为 $N$ 的线性前缀拆分为 $O(\text{log} N)$ 个特定长度的独立区间贡献之和。我们将这一思想强行平移到线段树的逻辑拓扑上：

树状数组节点 $i$ 管辖的内层权值线段树，其维护的内容是：原序列中下标在区间 $[i - \text{lowbit}(i) + 1, i]$ 内部的所有元素的频次分布总和。

2. 渐进时间与空间复杂度证明

$$T_{update} = O(\text{log} N \times \text{log} U)$$

$$cnt = \sum_{i \text{ in Nodes}(R)} tree[ls[i]] - \sum_{j \text{ in Nodes}(L-1)} tree[ls[j]]$$

单次查询时间复杂度严格为 $O(\text{log} N \times \text{log} U)$。

状态设计与算法推导

1. 外层拓扑与核心算子

外层基于 lowbit(x) = x & (-x) 执行拓扑跳转。定义两个全局指针数组 temp_L[] 和 temp_R[]，分别用于在查询时静态封存 $L-1$ 和 $R$ 对应的外层线段树根节点编号。

2. 区间修改（Modify）

定义函数 modify(pos, val, val_cnt)。其中 pos 为原序列下标，val 为离散化后的值域排名，val_cnt 为频次变化量（添加为 $+1$，删除为 $-1$）：

void modify(int pos, int val, int val_cnt) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        update(bit[i], 1, tot, val, val_cnt); // bit[i] 是该外层槽位对应的内层线段树根节点
    }
}

3. 多指针同步树上二分（Query_Kth）

查询时，先通过 for (int i = r; i > 0; i -= lowbit(i)) 将所有对应的内层根节点物理编号压入 temp_R 中（temp_L 同理）。定义递归函数 query_kth(1, tot, k)：

  1. 若 $l = r$，收敛返回。
  2. 核心代数求和：遍历 temp_R 数组中所有当前指针的左子节点，累加其 tree 值；随后遍历 temp_L 数组减去对应左子节点 tree 值。得到差值和 $left\text{_}sum$。
  3. 条件分支判定：

C++ 标准源码（NOIP风格：带修改区间第 K 大）

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

inline int read() {
    int x = 0, f = 1;
    char ch = getchar();
    while (ch < '0' || ch > '9') {
        if (ch == '-') f = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x << 3) + (x << 1) + (ch ^ 48);
        ch = getchar();
    }
    return x * f;
}

const int MAXN = 100005;
// 空间估算：N + M 次操作，外层 logN 约 17，内层 logU 约 17。
// 每次修改贡献 17 * 17 = 289 个节点。总节点数开到 MAXN * 400。
const int MAX_NODES = MAXN * 400;

struct Query {
    int opt; // 1 为修改，2 为查询
    int l, r, k;
} q[MAXN];

int n, m, tot;
int a[MAXN], raw_v[MAXN << 1]; // 离散化数组包含原数组和修改后的新数据

// 内层动态开点权值线段树结构
int bit[MAXN]; // 存储外层树状数组各槽位对应的内层树根节点编号
int tree[MAX_NODES], ls[MAX_NODES], rs[MAX_NODES];
int cnt = 0;

// 辅助指针数组，用于多树同步二分
int temp_L[40], temp_R[40];
int cnt_L, cnt_R;

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

void update(int &u, int l, int r, int val, int val_cnt) {
    if (!u) u = ++cnt;
    tree[u] += val_cnt;
    if (l == r) return;
    int m = (l + r) >> 1;
    if (val <= m) update(ls[u], l, m, val, val_cnt);
    else update(rs[u], m + 1, r, val, val_cnt);
}

// 外层增量控制
void modify(int pos, int val, int val_cnt) {
    for (int i = pos; i <= n; i += lowbit(i)) {
        update(bit[i], 1, tot, val, val_cnt);
    }
}

// 核心：多指针同步树上二分
int query_kth(int l, int r, int k) {
    if (l == r) return l;
    int m = (l + r) >> 1;

    // 计算当前区间内，所有外层关联树的左子树频次代数和
    int left_sum = 0;
    for (int i = 1; i <= cnt_R; ++i) left_sum += tree[ls[temp_R[i]]];
    for (int i = 1; i <= cnt_L; ++i) left_sum -= tree[ls[temp_L[i]]];

    if (k <= left_sum) {
        // 同步将所有有效指针推向左子节点
        for (int i = 1; i <= cnt_R; ++i) temp_R[i] = ls[temp_R[i]];
        for (int i = 1; i <= cnt_L; ++i) temp_L[i] = ls[temp_L[i]];
        return query_kth(l, m, k);
    } else {
        // 同步将所有有效指针推向右子节点，并扣除左侧贡献排名
        for (int i = 1; i <= cnt_R; ++i) temp_R[i] = rs[temp_R[i]];
        for (int i = 1; i <= cnt_L; ++i) temp_L[i] = rs[temp_L[i]];
        return query_kth(m + 1, r, k - left_sum); // 致命踩坑点：必须消减排名参数 k
    }
}

int main() {
    n = read(); int m_ops = read();
    int v_cnt = 0;
    for (int i = 1; i <= n; ++i) {
        a[i] = read();
        raw_v[++v_cnt] = a[i];
    }

    int q_cnt = 0;
    for (int i = 1; i <= m_ops; ++i) {
        char type;
        cin >> type;
        if (type == 'Q') {
            int l = read(), r = read(), k = read();
            q[++q_cnt] = {2, l, r, k};
        } else {
            int pos = read(), val = read();
            q[++q_cnt] = {1, pos, val, 0};
            raw_v[++v_cnt] = val; // 修改的目标新值也必须加入全局离散化
        }
    }

    // 完备离散化
    sort(raw_v + 1, raw_v + v_cnt + 1);
    tot = unique(raw_v + 1, raw_v + v_cnt + 1) - (raw_v + 1);

    // 初始化外层结构
    for (int i = 1; i <= n; ++i) {
        int pos = lower_bound(raw_v + 1, raw_v + tot + 1, a[i]) - raw_v;
        modify(i, pos, 1);
    }

    for (int i = 1; i <= q_cnt; ++i) {
        if (q[i].opt == 1) {
            // 动态单点修改：先在对应外层链中删除旧值频次，再插入新值频次
            int old_pos = lower_bound(raw_v + 1, raw_v + tot + 1, a[q[i].l]) - raw_v;
            modify(q[i].l, old_pos, -1); // 抹除

            a[q[i].l] = q[i].r; // 物理更新原序列
            int new_pos = lower_bound(raw_v + 1, raw_v + tot + 1, q[i].r) - raw_v;
            modify(q[i].l, new_pos, 1);  // 重构挂载
        } else {
            // 收集外层跳转序列的当前内层根节点指针
            cnt_L = 0; cnt_R = 0;
            for (int j = q[i].r; j > 0; j -= lowbit(j)) temp_R[++cnt_R] = bit[j];
            for (int j = q[i].l - 1; j > 0; j -= lowbit(j)) temp_L[++cnt_L] = bit[j];

            int ans_idx = query_kth(1, tot, q[i].k);
            printf("%d\n", raw_v[ans_idx]);
        }
    }
    return 0;
}

NOIP 实战避坑指南

1. 指针多树同步跳转时的引用污染与退化

在 query_kth 的分支重定向中，我们执行了 temp_R[i] = ls[temp_R[i]]。选手常犯的一个低级致命错误是：在计算 left_sum 时，未提前将所有指针完全收集，而是试图在递归内部动态计算外层 lowbit。这会导致在某一层二分转向右子树后，原本应该被消减的左子树指针状态在递归栈回溯时发生毁灭性的对位错置。必须在外部前置提取指针数组，且跳转时进行一刀切的物理覆盖。

2. 空间上限 MAX_NODES 估算不足引发线上爆零

树套树的空间复杂度是二维对数级别的（$O(M \text{log} N \text{log} U)$）。在 NOIP 级别的数据下（$N, M \text{ <= } 10^5$），如果将空间仅仅开到和标准主席树相同的 $N \times 25$，程序在线上评测跑完前几个纯查询点后，一旦遇到密集的修改点，++cnt 会瞬间将整个内存基数顶穿，触发 RE。必须严格开到 $N \times 400$ 左右，确保内存空间在物理配额上限内顶格分配。

3. 修改操作时忘记同步更新原序列数组 a[]

在执行单点修改操作时，我们需要调用 modify(pos, old_val, -1)。如果只执行了外层线段树的增减，而忘记了执行 a[pos] = new_val 来物理更新原序列，那么下一次如果对同一个位置再次发起修改时，代码将无法通过 a[pos] 获取到真正的“当前旧值”，从而减掉了一个错误的过时数据，导致整棵权值树的计数逻辑彻底被脏数据污染。

经典 NOIP/洛谷 真题

1. 洛谷 P2617 Dynamic Rankings 【模板】动态区间第 K 位

2. 洛谷 P3380 【模板】二逼平衡树（树套树精细控制版）

原文链接： local://7.4
[h] 返回首页
© 2026 Nefut. | 关于我们 | 联系我们 | 隐私政策 | RSS