【数据结构】树状数组及查询第K小的数

• 宏定义lowbit函数

#define lowbit(x) ((x) & (-x))

• add函数，更新当前元素时将所有可分解出当前数的元素均加上 v

void add(int x, int v) {
    for (int i = x; i < N; i += lowbit(i)) c[i] += v;
}

• getSum函数，得到前x个元素累加和

int getSum(int x) {
    if (x < 1) return 0;
    else return c[x] + getSum(x - lowbit(x));
}

• 树状数组完整实现与应用：查询第K小的数

#include <iostream>
#include <vector>
#define lowbit(x) ((x) & (-x))
using namespace std;
const int N = 1025;
int c[N] = {0};
void add(int x, int v) {
    for (int i = x; i < N; i += lowbit(i)) c[i] += v;
}
int getSum(int x) {
    if (x < 1) return 0;
    else return c[x] + getSum(x - lowbit(x));
}
int getKthLeast(int k) {
    int left = 1, right = N - 1, mid;
    while (left < right) {
        mid = (left + right) / 2;
        if (getSum(mid) >= k) right = mid;
        else left = mid + 1;
    }
    return left;
}
int main() {
    int n, k, temp, cnt = 0;
    while (true) {
        while (cin >> temp, temp != -1) {
            add(temp, 1);
        }
        printf("Input the k to search: ");
        scanf("%d", &k);
        if (k != -1) {
            printf("The k-th least number is %d\n", getKthLeast(k));
            break;
        } else continue;
    }
    return 0;
}