Algoogle

Algorithm for Programming Contest

Segment Tree

基本情報


計算量(RMQ)
用途 区間に対するクエリの処理

N := 区間の幅

解説


Segment Treeは主に区間に対するクエリを処理するために使われる.
完全二分木で実装されるので各クエリの計算量はO(log N)になる.
自由度が高く, 区間を扱う様々なものに利用される.
コードはRMQとその区間足し込みバージョンの実装.
この2つの書き方をなんとなくイメージできればある程度柔軟に実装できるようになるでしょう.
区間足し込みはその区間全体に一気に足された数というのを遅延評価することで実現できる.

コード


(segtree.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct segtree {
    int N, dat[2*MAX];
    segtree() {}
    segtree(int n) {
        N = 1;
        while(N < n) N *= 2;
        for(int i = 0; i < 2*N-1; i++)
            dat[i] = inf;
    }
    // update k th element
    void update(int k, int a) {
        k += N-1; // leaf
        dat[k] = a;
        while(k > 0) {
            k = (k - 1) / 2;
            dat[k] = min(dat[k*2+1], dat[k*2+2]);
        }
    }
    // min [a, b)
    int query(int a, int b) { return query(a, b, 0, 0, N); }
    int query(int a, int b, int k, int l, int r) {
        if(r <= a or b <= l) return inf;
        if(a <= l and r <= b) return dat[k];
        int m = (l + r) / 2;
        return min(query(a, b, k*2+1, l, m), query(a, b, k*2+2, m, r));
    }
};
(segtree2.cpp) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
struct segtree {
    int N;
    vector<int> dat, sum;
    segtree(int n) {
        N = 1;
        while(N < n) N <<= 1;
        dat.assign(2*N-1,0);
        sum.assign(2*N-1,0);
    }
    void add(int a, int b, int x) { add(a,b,x,0,0,N); }
    int add(int a, int b, int x, int k, int l, int r) {
        if(b <= l or r <= a) return dat[k];
        if(a <= l and r <= b) {
            sum[k] += x;
            return dat[k] += x;
        }
        int m = (l+r)/2;
        return dat[k] = min(add(a,b,x,2*k+1,l,m),add(a,b,x,2*k+2,m,r))+sum[k];
    }
    int minimum(int a, int b) { return minimum(a,b,0,0,N); }
    int minimum(int a, int b, int k, int l, int r) {
        if(b <= l or r <= a) return 1e9;
        if(a <= l and r <= b) return dat[k];
        int m = (l+r)/2;
        return min(minimum(a,b,2*k+1,l,m),minimum(a,b,2*k+2,m,r))+sum[k];
    }
};

問題


Comments