C++ 区间查询第 K 小的数：算法实现与优化

问题描述: 给定一个序列N及N个整数，有两种操作：

(1) A P V: 将第P个整数增加V。 (2) Q L R K: 查询区间[L, R]中第K小的数据。

输入格式:

第一行一个整数N表示序列中元素的个数。第二行N个整数表示序列中的元素。第三行一个整数Q表示操作的个数。接下来Q行，每行描述一个操作。操作分为两种：

'1 P V' 表示将第P个数加上V。 '2 L R K' 表示查询区间[L, R]中第K小的数。

输出格式:

对于每个查询操作，输出一行表示查询结果。如果查询结果不存在，则输出'-1'。

输入样例:

输出样例:

3
4

提示:

1<=N,Q<=100000; 1<=P<=N; 1<=L<=R<=N; 1<=K<=R-L+1; -1000000<=V<=1000000; 输入数据保证不会导致整型变量溢出。

算法实现:

该问题可以使用线段树或树状数组来解决。以下以线段树为例，实现C++代码：

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

using namespace std;

const int MAXN = 100005;

struct Node {
    int l, r;
    int val;
};

vector<Node> tree;
vector<int> arr;

void build(int l, int r, int idx) {
    tree[idx].l = l;
    tree[idx].r = r;
    if (l == r) {
        tree[idx].val = arr[l];
        return;
    }
    int mid = (l + r) / 2;
    build(l, mid, idx * 2);
    build(mid + 1, r, idx * 2 + 1);
    tree[idx].val = tree[idx * 2].val + tree[idx * 2 + 1].val;
}

void update(int pos, int val, int idx) {
    if (tree[idx].l == tree[idx].r && tree[idx].l == pos) {
        tree[idx].val = val;
        return;
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (pos <= mid) {
        update(pos, val, idx * 2);
    } else {
        update(pos, val, idx * 2 + 1);
    }
    tree[idx].val = tree[idx * 2].val + tree[idx * 2 + 1].val;
}

int query(int l, int r, int idx, int k) {
    if (tree[idx].l == l && tree[idx].r == r) {
        if (k <= tree[idx].val) {
            return tree[idx].val;
        } else {
            return -1;
        }
    }
    int mid = (tree[idx].l + tree[idx].r) / 2;
    if (r <= mid) {
        return query(l, r, idx * 2, k);
    } else if (l > mid) {
        return query(l, r, idx * 2 + 1, k);
    } else {
        int left = query(l, mid, idx * 2, k);
        if (left != -1) {
            return left;
        }
        int right = query(mid + 1, r, idx * 2 + 1, k - left);
        return right;
    }
}

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

优化技巧:

使用二分查找优化查询操作，可以将时间复杂度降低到O(logN)。
使用离散化将数据范围压缩，可以减少内存占用。
使用动态开点线段树，可以将空间复杂度降低到O(NlogN)。

总结:

本文介绍了使用线段树解决区间查询第K小的数问题的算法实现与优化技巧。在实际应用中，可以根据具体情况选择合适的算法和优化技巧来提高程序的性能。

相关问题:

LeetCode 307. 区域和检索 - 数组可修改
LeetCode 303. 区域和检索 - 数组不可修改
LeetCode 315. 计算右侧小于当前元素的个数
LeetCode 703. 数据流中的第 K 个最大元素

进一步学习:

线段树：https://www.geeksforgeeks.org/segment-tree-set-1-sum-of-given-range/
树状数组：https://www.geeksforgeeks.org/binary-indexed-tree-or-fenwick-tree-2/
离散化：https://www.geeksforgeeks.org/discrete-mathematics-set-1/

注:

本代码示例仅供参考，具体的算法实现和优化技巧需要根据实际情况进行调整。