NeFut Logo NeFut
中 Admin Login

Efficient Solution to Dynamic Range K-th Largest Problem: Combining Fenwick Tree and Segment Tree

Published at: 2026-05-27 09:17 Last updated: 2026-06-10 09:27
#C++ #Tutorial

Core Logic and Mathematical Principles

In Section 7.3, we perfectly solved the static K-th largest problem in a range with a complexity of $O(\text{log} N)$ using the prefix sum and difference properties of persistent segment trees (president trees). However, once the problem introduces dynamic point updates (e.g., modifying the $i$-th number in the original sequence to $X$), the prefix sum chain of the static president tree will be completely broken. Modifying one number in the sequence will invalidate all subsequent prefix versions ($Root[i]$ to $Root[N]$). If we force reconstruction, the time complexity for a single modification will degrade to $O(N \text{log} N)$.

Fenwick Tree serving Dynamically Allocated Value Segment Trees, also known as the modified president tree, is a breakthrough solution to this dynamic high-dimensional retrieval problem.

1. Dimensional Degeneration of Classic Dynamic Prefix Sums

In the face of dynamic prefix sum modifications, the most mature foundational algorithm is the Fenwick Tree (Lowbit Optimization). The Fenwick Tree splits a linear prefix of size $N$ into the sum of $O(\text{log} N)$ independent intervals of specific lengths. We forcibly translate this idea into the logical topology of segment trees:

The inner weighted segment tree governed by Fenwick Tree node $i$ maintains the content: the total frequency distribution of all elements in the original sequence with indices in the range $[i - \text{lowbit}(i) + 1, i]$.

2. Asymptotic Time and Space Complexity Proof

$$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]]$$

The time complexity for a single query is strictly $O(\text{log} N \times \text{log} U)$.

State Design and Algorithm Derivation

1. Outer Layer Topology and Core Operators

The outer layer executes topological jumps based on lowbit(x) = x & (-x). Define two global pointer arrays temp_L[] and temp_R[] to statically store the root node indices of the outer segment trees corresponding to $L-1$ and $R$ during queries.

2. Range Modification (Modify)

Define the function modify(pos, val, val_cnt). Here, pos is the index of the original sequence, val is the discretized value ranking, and val_cnt is the frequency change (added as $+1$, removed as $-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] is the root node of the inner segment tree corresponding to this outer slot
    }
}

3. Multi-Pointer Synchronous Binary Search on Tree (Query_Kth)

During the query, first push all corresponding inner root node physical indices into temp_R using for (int i = r; i > 0; i -= lowbit(i)) (similarly for temp_L). Define the recursive function query_kth(1, tot, k):

  1. If $l = r$, converge and return.
  2. Core algebraic summation: Traverse all current pointers' left child nodes in the temp_R array, accumulating their tree values; then traverse the temp_L array to subtract the corresponding left child tree values. Obtain the difference and set it as $left\text{_}sum$.
  3. Conditional branching judgment:

C++ Standard Source Code (NOIP Style: K-th Largest in Modified Range)

#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;
// Space estimation: N + M operations, outer layer logN about 17, inner layer logU about 17.
// Each modification contributes 17 * 17 = 289 nodes. Total node count is set to MAXN * 400.
const int MAX_NODES = MAXN * 400;

struct Query {
    int opt; // 1 for modification, 2 for query
    int l, r, k;
} q[MAXN];

int n, m, tot;
int a[MAXN], raw_v[MAXN << 1]; // Discretization array includes original array and new modified data

// Inner dynamically allocated weighted segment tree structure
int bit[MAXN]; // Stores the root node indices of the inner trees corresponding to each slot of the outer Fenwick Tree
int tree[MAX_NODES], ls[MAX_NODES], rs[MAX_NODES];
int cnt = 0;

// Auxiliary pointer arrays for multi-tree synchronous binary search
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);
}

// Outer layer incremental control
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);
    }
}

// Core: Multi-pointer synchronous binary search on tree
int query_kth(int l, int r, int k) {
    if (l == r) return l;
    int m = (l + r) >> 1;

    // Calculate the total frequency sum of all outer associated trees' left subtrees in the current range
    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) {
        // Synchronize to push all effective pointers to left child nodes
        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 {
        // Synchronize to push all effective pointers to right child nodes and reduce left contribution ranking
        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); // Critical pitfall: must reduce ranking parameter 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; // The target new value of modification must also be included in global discretization
        }
    }

    // Complete discretization
    sort(raw_v + 1, raw_v + v_cnt + 1);
    tot = unique(raw_v + 1, raw_v + v_cnt + 1) - (raw_v + 1);

    // Initialize outer structure
    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) {
            // Dynamic point modification: first delete the old value frequency in the corresponding outer chain, then insert the new value frequency
            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); // Erase

            a[q[i].l] = q[i].r; // Physically update the original sequence
            int new_pos = lower_bound(raw_v + 1, raw_v + tot + 1, q[i].r) - raw_v;
            modify(q[i].l, new_pos, 1);  // Reconstruct mount
        } else {
            // Collect the current inner root node pointers of the outer jump sequence
            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 Practical Pitfalls Guide

1. Reference Pollution and Degradation during Multi-Tree Synchronous Jumps of Pointers

In the branching redirection of query_kth, we executed temp_R[i] = ls[temp_R[i]]. A common low-level fatal error made by contestants is: when calculating left_sum, failing to fully collect all pointers in advance and instead attempting to dynamically calculate the outer lowbit within the recursion. This can lead to devastating misalignment of the left subtree pointer state during the recursive stack backtracking after a right subtree redirection at a certain level of binary search. It is crucial to extract the pointer array externally in advance and perform a wholesale physical overwrite during the jump.

2. Insufficient Estimation of Space Limit MAX_NODES Leading to Runtime Errors

The space complexity of tree-on-tree is at a two-dimensional logarithmic level ($O(M \text{log} N \text{log} U)$). Under NOIP-level data (with $N, M \text{ <= } 10^5$), if the space is only allocated to match the standard president tree at $N \times 25$, the program will run through the first few pure query points in online evaluation and, once encountering dense modification points, ++cnt will instantly push the entire memory base over the top, triggering a runtime error (RE). It is essential to strictly allocate space to about $N \times 400$ to ensure that memory is maximally allocated within the physical quota limit.

3. Forgetting to Synchronize and Update the Original Sequence Array a[] During Modification Operations

When performing point modification operations, we need to call modify(pos, old_val, -1). If only the increment and decrement of the outer segment tree are executed without updating a[pos] = new_val to physically update the original sequence, the next time a modification is made to the same position, the code will be unable to obtain the true "current old value" through a[pos], thus subtracting an incorrect outdated data, leading to the entire weighted tree's counting logic being thoroughly polluted by dirty data.

Classic NOIP/Luogu Problems

1. Luogu P2617 Dynamic Rankings 【Template】Dynamic K-th in Range

2. Luogu P3380 【Template】Boring Balanced Tree (Fine Control Version of Tree-on-Tree)

Original Source: local://7.4
[h] Back to Home
© 2026 Nefut. | About Us | Contact Us | Privacy Policy | RSS