C++ 实现区间查询第 K 小数：线段树 + 离散化

本题可以使用线段树+离散化解决。

线段树的每个节点维护一个区间内的数的信息，包括最大值、最小值、区间和、区间内数的个数等等。同时，我们用一个数组来保存原始的序列，那么线段树的根节点维护的就是整个序列的信息。

对于每个操作，我们需要分别处理'加'和'查'两种情况。

对于'加'操作，我们需要将对应位置的数加上指定的值，并更新线段树维护的信息。具体来说，我们需要递归下去更新左右儿子的信息，然后根据左右儿子的信息更新当前节点的信息。

对于'查'操作，我们需要递归地进入左右儿子，根据它们维护的信息来判断应该往哪个儿子继续递归，直到找到第K小的数。具体来说，我们首先需要判断当前节点的区间是否完全包含查询区间，如果是，那么直接返回当前节点维护的第K小的数。如果不是，那么我们需要进入左右儿子，分别计算左右儿子维护的区间与查询区间的交集，然后根据左右儿子维护的信息以及交集的大小来决定应该往哪个儿子继续递归。具体来说，如果左儿子维护的区间与查询区间的交集大小不小于K，那么说明第K小的数在左儿子中，因此我们递归进入左儿子。否则，说明第K小的数在右儿子中，因此我们需要递归进入右儿子，同时将K减去左儿子维护的区间与查询区间的交集大小。

注意，在递归过程中，我们需要记录每个节点维护的区间的左右端点，以便在递归时计算左右儿子维护的区间与查询区间的交集。

时间复杂度

对于每个操作，我们需要递归O(logN)层，每层需要进行常数次操作，因此时间复杂度为O(QlogN)。

C++ 代码

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

const int MAXN = 100000 + 5;

struct Node {
    int l, r;
    int sum, cnt;
    Node *lc, *rc;
    Node(int l, int r) : l(l), r(r), sum(0), cnt(0), lc(NULL), rc(NULL) {}
};

Node *build(int l, int r) {
    Node *node = new Node(l, r);
    if (l == r) return node;
    int mid = (l + r) >> 1;
    node->lc = build(l, mid);
    node->rc = build(mid + 1, r);
    return node;
}

void update(Node *node, int pos, int val) {
    if (node->l == node->r) {
        node->sum += val;
        node->cnt = 1;
        return;
    }
    int mid = (node->l + node->r) >> 1;
    if (pos <= mid) update(node->lc, pos, val);
    else update(node->rc, pos, val);
    node->sum = node->lc->sum + node->rc->sum;
    node->cnt = node->lc->cnt + node->rc->cnt;
}

int query(Node *node, int l, int r, int k) {
    if (l <= node->l && node->r <= r) {
        if (node->cnt < k) return -1;
        if (node->l == node->r) return node->sum;
        int leftCnt = node->lc->cnt;
        if (leftCnt >= k) return query(node->lc, l, r, k);
        else return query(node->rc, l, r, k - leftCnt);
    }
    int mid = (node->l + node->r) >> 1;
    int leftCnt = 0, rightCnt = 0;
    if (l <= mid) leftCnt = query(node->lc, l, r, k);
    if (rightCnt < k && r >= mid + 1) rightCnt = query(node->rc, l, r, k - leftCnt);
    if (leftCnt != -1) return leftCnt;
    if (rightCnt != -1) return rightCnt;
    return -1;
}

int main() {
    int n, q;
    cin >> n;
    vector<int> a(n + 1);
    for (int i = 1; i <= n; i++) cin >> a[i];
    cin >> q;
    Node *root = build(1, n);
    for (int i = 1; i <= n; i++) update(root, i, a[i]);
    while (q--) {
        int op, p, v, l, r, k;
        cin >> op;
        if (op == 1) {
            cin >> p >> v;
            update(root, p, v);
        } else if (op == 2) {
            cin >> l >> r >> k;
            cout << query(root, l, r, k) << endl;
        }
    }
    return 0;
}