PAT 真题 | 1057 Stack

这道题用到了一个 ACM 赛题中常见的数据结构——树状数组, 又称 Binary Index Tree.
PAT 1057 Stack

题目分析

让我们记录一个栈中的数据的中位数. 如果使用传统的前缀和方法，更新时的复杂度为O(n)，复杂度较大。考虑用一个辅助数组 c 来实现树状数组, 为了方便理解, 假设 c 对应的原始数组为 a[i]. 那么 a[i] 记录的是大小为 i 的数据的个数. 树状数组能对 a[0] … a[i] 的值进行O(lg n)时间复杂度的求和, 这个和表示的就是值小于等于 i 的数据的个数. 当这个和等于 (int)读入所有元素的个数/2 时, i 对应的就是中位数了.

树状数组的存储方式比较简单, 但是操作非常有技巧, 首先就是获取某数的二进制表示下最低的 1 对应数.

#define lowbit(x) ((x) & (-x))
int c[maxn];    // 树状数组

当Push一个数 temp 后, 我们对树状数组进行更新就可以这样写，v=1:

void update(int start, int v) {
    for(int i = start; i < maxn; i += lowbit(i)){
        c[i] += v;  // v是增加/减少的个数
    }
}

如果是Pop就把v=1变为-1即可.

如果要统计小于等于 x 的键值个数 sum, 复杂度也是 O(log n).

int askSum(int x) {
    int sum = 0;
    for(int i = x; i; i -= lowbit(i)){
        sum += c[i];
    }
}

在查找最小为target的位置时使用二分查找的思想, 效率会更高.

// target 表示中位数的位置，（若栈中数据个数n，则target=(n+1)/2）
int medianSearch(int target) {
    int left = 0, right = maxn-1;
    while(left < right){
        int mid = left + (right-left)/2;
        if (askSum(mid) >= target){
            right = mid;
        } else {
            left = mid + 1;
        }
    }
    return left;
}

参考资料：
[1]: 完全理解并深入应用树状数组 | 支持多种动态维护区间操作
[2]: 柳婼 の blog