树状数组、分桶法、线段树

刷题目有段时间了，发现最难得还是模拟。但是也有很多简单问题可以用朴素的空间换时间来大幅加速，看了很多高手的解题报告，发现了这些想法，很典型的是分桶法和树状数组(之后更新了线段树)，做一下总结，希望以后自己能活用在其他问题上。

题目是PAT1057 Stack
只是插入和排序找中位数会超时，稍微做变化，有两种方法。

分桶法

使用数轴hash的方法，求前缀和，在这之前再分块便于搜索，用一个数组记录每块有几个数，块长×块数=总数，时间复杂度O(块长+块数)。
类似想法的还有 PAT1095 Cars on Campus使用一天的时间轴time[24×60×60],进门axis[intime]++ 出门axis[outime]— 任意时刻的校园内车的数量只要求前缀和就可以了。


#include<string>
#include<stack>

using namespace std;
const int total = 100000;
const int everybk = 500;
int buckets[total / everybk][everybk];
int cnt[total / everybk] = { 0 };//every bucket count
stack<int>s;
void () {
    int count = 0,buk,i;
    int size = (s.size() % 2 == 0) ? s.size() / 2: (s.size()+1) / 2;
    for (buk=0; buk < total / everybk; buk++) {
        if (cnt[buk] + count >= size) break;
        count += cnt[buk];
    }
    for (i = 0; i < everybk; i++) {
        count += buckets[buk][i];
        if (count >= size) {
            cout << buk * everybk + i << endl;
            return;
        }
    }
}
int main() {
    int n;
    scanf("%d", &n); char str[11]; 
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        if (str[1] == 'o') { 
            if (s.empty())cout << "Invalid" << endl;
            else {
                int temp = s.top();
                buckets[temp / everybk][temp % everybk]--;
                cnt[temp / everybk]--; 
                cout << temp << endl;
                s.pop();
            }
        }
        else if (str[1] == 'e') {
            if(s.empty())cout << "Invalid" << endl;
            else median();
        }
        else {
            int temp;
            scanf("%d", &temp);
            buckets[temp / everybk][temp % everybk]++;
            cnt[temp / everybk]++;
            s.push(temp);
        }
    }
    return 0;
}

树状数组也是一种快速求前缀和的方法，利用lowbit(i){ i & -i;}求出i的二进制表示中最低位的1所表示的数。
5 & -5 = 0000 0101 & 1111 1011 = 0000 0001 = 1
4 & -4 = 0000 0100 & 1111 1100 = 0000 0100 = 4
如此其实可以将任意一个数用lowbit()将其中的1去掉。
求前7个前缀和:
sum[7]=A[1]+A[2]+A[3]+A[4]+A[5]+A[6]+A[7] ;
C[4]=A[1]+A[2]+A[3]+A[4]; C[6]=A[5]+A[6]; C[7]=A[7];
sum[7]=C[4]+C[6]+C[7];
sum[(111)]=C[(100)]+C[(110)]+C[(111)];

因此自上而下求和，自下而上更新。


#include <stack>
using namespace std;
const int maxn = 100010;
int arr[maxn];
stack<int>s;
int lowbit(int i) { return i & -i; }
void update(int index, int val) {
    while (index <= maxn) {
        arr[index] += val;
        index += lowbit(index);
    }
}
int getsum(int index) {
    int result = 0;
    while (index > 0) {
        result += arr[index];
        index -= lowbit(index);
    }
    return result;
}
void PeekMedian() {
    int low = 1, high = maxn, mid;
    int k = s.size()%2 == 0? s.size()/2:(s.size()+1)/2;
    while (low <= high) {
        mid = (low + high) / 2;
        if (getsum(mid) >= k)high = mid - 1;
        else low = mid + 1;
    }
    printf("%dn", low);
}
int main() {
    int n, temp;
    scanf("%d", &n);
    char str[15];
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        if (str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(temp, 1);
        }
        else if (str[1] == 'o') {
            if (!s.empty()) {
                update(s.top(), -1);
                printf("%dn", s.top());
                s.pop();
            }
            else printf("Invalidn");
        }
        else {
            if (!s.empty()) PeekMedian();
            else printf("Invalidn");
        }
    }
    return 0;
}

线段树

线段树在此题可以在logN内求任意区间内的点个数。在此用感觉并不太合适。
这里有两种线段树的实现，普通递归的实现和作为学习摘录的zkw线段树(无递归)。

普通递归


#include <stack>
using namespace std;
const int maxn = 100010;
int segtree[4*maxn];
int n;
stack<int>s;
int query(int l, int r, int k,int kth) {
    if (l == r) return l;
    int mid = (l + r) >> 1;
    if (segtree[k << 1] >= kth) return query(l, mid, k << 1, kth);
    else return query(mid + 1, r, k << 1 | 1, kth - segtree[k << 1]);
}

void update(int l, int r, int k, int index, int val) {
    if (l == r) {
        segtree[k] += val;
        return;
    }
    int mid = (l + r) >> 1;
    if (index <= mid) update(l, mid, k << 1, index, val);
    else update(mid + 1, r, k << 1 | 1, index, val);
    segtree[k] = segtree[k << 1] + segtree[k << 1 | 1];
}
int main() {
    int temp;
    scanf("%d", &n);
    char str[15];
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        if (str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            update(0, maxn, 1, temp, 1);
        }
        else if (str[1] == 'o') {
            if (!s.empty()) {
                update(0, maxn, 1, s.top(), -1);
                printf("%dn", s.top());
                s.pop();
            }
            else printf("Invalidn");
        }
        else {
            if (!s.empty()) {
                int kth = s.size() % 2 == 0 ? s.size() / 2 : (s.size() + 1) / 2;
                printf("%dn",query(0, maxn, 1, kth));
            }
            else printf("Invalidn");
        }
    }
    return 0;
}

zkw线段树

#include <cstdio>
#include <stack>
using namespace std;

typedef int Node;
class zkw_segtree{
private:
    Node *T;
    int size;
public:
    zkw_segtree(int range){
        for (size = 1; size < range + 2; size <<= 1);
        T = new Node[2 * size];
        for (int i = 1; i < size + size; i++)
            T[i] = 0;
    }

    void Add(int value, int i){
        for (i += size; i; i >>= 1)
            T[i] += value;
    }

    int Query(int s, int t){
        int ret = 0;
        for (s += size - 1, t += size + 1; s^t ^ 1; s >>= 1, t >>= 1){
            if (~s ^ 1) ret += T[s ^ 1];
            if (t ^ 1)  ret += T[t ^ 1];
        }
        return ret;
    }

    int Find_Kth(int k, int root = 1){
        while (root << 1 < size << 1){
            if (T[root << 1] >= k)  root = root << 1;
            else{
                k -= T[root << 1];
                root = (root << 1) + 1;
            }
        }
        return root - size;
    }

    ~zkw_segtree(){
        delete[] T;
    }
};
zkw_segtree segtree(100000);
int main(){
    int temp, n;
    stack<int>s;
    scanf("%d", &n);
    char str[15];
    for (int i = 0; i < n; i++) {
        scanf("%s", str);
        if (str[1] == 'u') {
            scanf("%d", &temp);
            s.push(temp);
            segtree.Add(1, temp);
        }
        else if (str[1] == 'o') {
            if (!s.empty()) {
                segtree.Add(-1, s.top());
                printf("%dn", s.top());
                s.pop();
            }
            else printf("Invalidn");
        }
        else {
            if (!s.empty()) 
                printf("%dn",segtree.Find_Kth((s.size() + 1) / 2));
            else printf("Invalidn");
        }
    }
    return 0;
}

树状数组、分桶法、线段树

分桶法

树状数组

线段树

普通递归

zkw线段树

近期文章

近期评论

标签

热门

文章归档

分类目录

功能