ACM_kirakira: Segment Tree + BIT (Fenwick Tree) In Deep

今天GCJ Round 1C也GG了...要是早點交A-large 或者不做C-small...應該就過了...
看來要拿T-Shirt還有段距離, 明年請早 :"(

回到正常的步伐, 繼續原本計劃好的學習旅程
(大學時期每次打完比賽都會頹廢很久, 現在能直視自己的失敗真的感恩)

再來一篇記Concept / 技巧的文...
(因為這陣子除了GCJ都沒怎樣打完整的比賽, 較少比賽題目的紀錄)

這篇是針對Segment Tree 和 BIT 的一些深一步的了解而寫的

說是In Deep其實也是一些對Div.1 玩家來說很common的東東

其中有些concept我也不是100%肯定但暫時理解是這樣

Segment Tree + BIT (Fenwick Tree) In Deep

首先故事是這樣的, 萬惡也是從Stack Overflow開始

我閑逛Stack Overflow的時候, 看到了一題有關SPOJ的題目

是關於Segment Tree的, 由於該問發問者的名稱很不錯 (叫Wen_dy)

我決定看一下, 發現是很赤裸的Segment Tree題目

Range Add Value
Range Query Sum

題目在此: http://www.spoj.com/problems/HORRIBLE/

BIT (Fenwick Tree) Part

本想借此重溫一下Segment Tree...沒想到一下子就卡住了

才發現根本一直都沒搞清楚Segment Tree的結構 (所謂沒搞清楚下面會再講)

然後更嚴重的是, 看了SPOJ下面的Comment, 竟然有人說可以用BIT做!

怎樣想也不懂...結果就跑去查了....

幸好找到了一個很好很好的BIT 說明 Reference:

https://kartikkukreja.wordpress.com/2013/12/02/range-updates-with-bit-fenwick-tree/
裡面還有一個更好的Reference, 是來自Quora的, 有信心保證:
http://programmingcontests.quora.com/Tutorial-Range-Updates-in-Fenwick-Tree

讓我引用一下裡面說的東西:

基本上, BIT出現的形式有3種:

Range Update Point Query . Point Update Range Query, 和最麻煩的Range Update Range Query

然後文中給出了頭2種基本的例子...大同小異的

Range Update Point Query
Point Update Range Query





然後就是重中之中, 這題目要用到的技巧: Range Update Range Query!

長話短說, 這個技巧是用上 兩個BIT Array去完成的

update(ft, p, v):
for (; p <= N; p += p&(-p))
ft[p] += v

# Add v to A[a...b]
update(a, b, v):
update(B1, a, v)
update(B1, b + 1, -v)
update(B2, a, v * (a-1))
update(B2, b + 1, -v * b)

query(ft, b):
sum = 0
for(; b > 0; b -= b&(-b))
sum += ft[b]
return sum

# Return sum A[1...b]
query(b):
return query(B1, b) * b - query(B2, b)

# Return sum A[a...b]
query(a, b):
return query(b) - query(a-1)

上面的Code中的B1 是普通的Range Update Point Query, 可以用它來Range Add和Query某一個位置的value a[p]

然後考慮一下 index p 的range, 來想一下Range Update [a,b] Add v 後

S[p] = Sum [1..p] 的值會怎樣


1 <= p < a : 0
a <= p <= b : v * (p – (a – 1))
b < p <= N : v * (b – (a – 1))

留意假設只有這個Update的話, 只有上面第2點的range內會有value, 其它的value 都是0

所以如果我們Query B1(p) 的話 (就如上面說的, 就是普通的Point Query, 所以是a[p])

再乘以p自己, 然後得出的值如下:

0
v*p
0

對比上面我們想要得到的算式 (就是Sum[1..p]的算式)

不難發現對於每個range, 其實也是 Query B1(p) * p 減去一個constant X:

0 - 0 = 0 --> X = 0
v*p - v*(a-1) = v*(p-(a-1)) --> X = v*(a-1)
0 - (-v*(b-(a-1))) = v*(b-(a-1)) --> X = -v*b + v(a-1)

B2 說白了, 就是儲存這個X的另一個 BIT (也是Range Update Point Query的形式)了

For 一個Update Query [a,b] + v:

B2 先 Update B2 (a, v*(a-1)) <---所有 >= a 的 index都有影響

再Update B2 (b, -v*b) <-- v*(a-1) 的部分上面包括了

那麼: Query(L,R) = Sum[1..R] - Sum[1..L-1]

= (Query(B1, R)*R - Query(B2, R)) - (Query(B1, L-1)*(L-1) - Query(B2, (L-1)))

(這兒順帶學習了C++一個很簡單的東西: 只要signature不同, function同名都可以, 於這兒不同種類的Update()/ Query() 利用會很方便)

再想個複雜一點的例子來說明Concept
假設現在有2個Range Query [a,b,v1] 和 [c,d,v2]

再假設現在想找 Sum[1..p] where p 只在 [c,d]內而不在[a,b]內

那麼Query(B1, p)*p 是多少? Query(B2, p) 又是多少?

Query(B1,p) = (0+v2) <--0是因為不受第一個Query影響

Query(B2,p) = -v1*b + v1*(a-1) + v2*(c-1)

所以

Query(B1, p)*p - Query(B2,p) = (0+v2)*p - (-v1*b + v1*(a-1) + v2*(c-1))

= 0 - (-v1*b+v1*(a-1)) + v2*p - v2*(c-1)

-->Sum[1..p] from Query 1 + Sum[1..p] from Query 2

其它Case也差不多可以這樣分解, 代表 n 個update 之後, 仍然可以用這個方法去Range Query的

道理上明白了, 最要緊是記得如何找出X, 自然就可以很簡單Code出來了

可惜BIT只能處理Add / Sum 之類的function...

下面是用這個變態技巧過 SPOJ Horrible的Code:

#include<bits/stdc++.h>
#define LL long long
using namespace std;

LL T, n, c, t,p,q, v;
LL bit1[100005], bit2[100005];

void add(LL* bit,int x, LL v){
    for(; x <= n; x+= x&(-x)) bit[x] += v;
}
void add(int x, int y, LL v){
    add(bit1,x, v); add(bit1,y+1, -v);
    add(bit2,x, v*(x-1)); add(bit2, y+1, -v*y);
}

LL query(LL *bit, int x){
    LL ret = 0;
    for(; x ; x-= x&(-x)) ret += bit[x];
    return ret;
}
LL query(int x){
    return query(bit1, x)*x - query(bit2, x);
}

LL query(int x, int y){
    return query(y) - query(x-1);
}

int main(){
    scanf("%I64d", &T);
    while(T--){
        memset(bit1,0,sizeof(bit1));
        memset(bit2,0,sizeof(bit2));
        scanf("%I64d%I64d", &n,&c);
        for(int i=0; i<c;i++){
            scanf("%I64d%I64d%I64d", &t, &p, &q);
            if(!t) scanf("%I64d", &v);
            
            if(!t) add(p,q,v);
            else printf("%I64d\n", query(p,q));
        }
    }
    return 0;   
}

Segment Tree Part

學完新技巧, 回歸原點, 我決定以Segment Tree再過這一題

(人家在Stack Overflow原文是求Segment Tree的答案嘛...)

才發現自己對Segment Tree的理解是如此低

當年開了頭學習了基本implementation, complexity等等的東東

但仍是不到位

這題 (Range Add, Range Query Sum) 我印象中算是很Standard了

也肯定在POJ Code過類似的題目, 但這時又忘了..

才更覺得要認真看待這個Data Structure, 問了GG後, 又再看了看一些Reference後

又有一些(好像)深一點的理解

我看的是這個Reference:

http://letuskode.blogspot.in/2013/01/segtrees.html

(裡面附送人家寫的Segment Tree STL, 但它的方式實在不合口味, 雖然是很強大, 還是學Concept算了...)

首先是這個神奇的, 似懂非懂的Term: Lazy Propagation

原來一直聽的這個詞, 是等價於另一些人可能會說的Terms, 例如: Split, Push Down

但其意思/ 意義是一樣的, 指向同一個"動作"

這個動作的原意是想避免每次Update / Query 都會去到葉子

經POJ某份PDF所說, 這樣好像可以去到O(N), 不懂Proof, 感覺也不對, 但總之就是很慢, 慢到會TLE的樣子 (for eg: Range Update [a,b], 如果每次都到葉子, implementation很簡單, 也肯定正確, 但就是太慢了, 要是[a,b] 每次都是 [1,n] 怎辦?)

所以就出現了這個方法: Lazy Propagation, 故名思意, 就是要用到 (Tranverse到那一個Segment Node) 時候才Update Node的Information

而Lazy Propagation 之外, 又有另一種常聽 / 見的字眼: Merge, Pull Up...

這又是Segment Tree內另一種動作, 跟Lazy Propagation相對的

究竟這2種動作是什麼來的, 如何運作, 何時使用?

有沒有一種Standard的Rule / Structure決定, 何時要用上這些動作呢...

按GG 和該Reference所說, 是有的

Segment Tree的 Update / Query 是有一定結構的, 在不斷試驗理解後, 應該是這樣的:

Range Update():

if (Current Segment covers the range){

update this node's info; return;
}

Split();

Recur Left / Right Son Part;

Merge();

}

Range Query():

if (Current Segment covers the range){

return this node's info
}

Split();

Recur Left / Right Son Part;

Merge();

}

當中Split() 跟Merge() 是把Info 推向下層兩個兒子, 和從下層兩個兒子算出current segment的Info用的

就是這樣了! 原來是很Standard / General 的結構, 但為何以前很多時候都可以沒有Split / Merge呢?

原因是這樣的, 視情況而定, Node 的 Info, Split 和Merge的Implementation 也是視題目而定的...這就是Segment Tree難搞的地方, 因為沒有萬能藥, 可以萬年通用的Rule / Implmentation

但是還是有多少事情可以深入理解下:

首先, 不難發現到, 會執行Split 的 Segment, 也會執行Merge

那麼該Segement的Info 已經 1. 推向下層 2. 最後會由下層算出正確的Info

所以在Split的時候基本上可以把Info Reset了

例如在Horrible中, 一個Segment Node的Info 是 Sum 跟 Add

代表該Segment的總和, 和Add在該Segment的 value

在Split的時候, 先把Add 加去下一層, 又把下一層的Sum 加上 Add的value

然後需要把Add reset做 0 !

這時, 該Segment的下面2個node 的Sum已經update了, 要是有query的range 剛好包括它們2個其中1個, 那麼就如上面所說的, 直接return sum 就可以了, 要是還要再向下一層, 那麼會在query時再Split下去, recur下去

然後所有曾經Split下去的Segment的Sum 又會在Merge的時候從下面2個兒子算出 (下面2個兒子的Sum肯定正確的, 因為Split到盡頭時的Sum一定正確, 然後沿路一直Merge上來)

把Add reset做 0 是因為可能下次會再Update 該Segment

然後又可能會再需要Split下去, 記住我們Split的時候是把當時該Segment的Add Split下去再算Sum的 (用+=) 所以如果不reset 做0, 會加多很多value去下一層...

(這些Node的Split / Update, Merge等等的東西, 我極度懷疑真的是每題題目都要度身訂做, 慢慢試一些test case去試出來)

簡單地說, 這種Split 跟Merge的結構, 在我們從根到某個node的path, 經過path上的node時才一直push down 和merge (要是需要的話), 沒經過的path (上的node) 就不管了

這樣當然速度會相當快, 也不會TLE

最後Base on上面對Split 跟Merge的理解, 我有以下的猜測:

要是Update和Query 有其中一個不是Range的話, Split 跟Merge可能不用Implement:

如果是Point Update, 可能不用Split了...但需要Merge

如果是Point Query, 可能不用Merge了, 但需要Split

80%肯定, 但沒有Proof

反正最大的得著就是: Segment Tree的Update跟Query有很好很Stable的結構

但Node design, Split()和Merge()的 Implementation就真的要看題目了...

最後是用Segment Tree (Lazy Propagation) 過SPOJ Horrible的Code:

可以特別留意Split(), Merge() 的Implementation

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T, n, c, p, q, v, t;

struct node
{
    int l,r,m;
    LL numleaves, add, sum;
    node(int l,int r, int m): l(l), r(r), m(m){
        add = sum = 0;
        numleaves = r-l+1;
    }
    node(){}
}tree[400010];

void build(int c, int u, int v){
    int m = (u+v)>>1;
    tree[c] = node(u,v, m);
    if(u == v) { tree[c].numleaves = 1; return;}
    build(2*c, u, m);
    build(2*c+1, m+1, v);
}

void push_down(int x){
    tree[2*x].add += tree[x].add;
    tree[2*x+1].add += tree[x].add;
    tree[2*x].sum += tree[x].add * tree[2*x].numleaves;
    tree[2*x+1].sum += tree[x].add * tree[2*x+1].numleaves;
    tree[x].add = 0;
}

void merge(int x){
    tree[x].sum = tree[2*x].sum + tree[2*x+1].sum;
}

void update(int c, int l, int r, int v){
    if(tree[c].l == l && tree[c].r == r){
        tree[c].add += v;
        tree[c].sum += v*tree[c].numleaves;
        return;
    }
    push_down(c);
    if(r <= tree[c].m) update(2*c, l,r, v);
    else if(l > tree[c].m) update(2*c+1, l,r, v);
    else{
        update(2*c, l, tree[c].m, v);
        update(2*c+1, tree[c].m+1, r, v);
    }
    merge(c);
}

LL query(int c, int l, int r){
    if(tree[c].l == l && tree[c].r == r){
        return tree[c].sum;
    }
    push_down(c);
    LL L,R; L = R = 0;
    if(r <= tree[c].m) L = query(2*c, l, r);
    else if(l > tree[c].m) R = query(2*c+1,l,r);
    else{
        L = query(2*c, l, tree[c].m);
        R = query(2*c+1, tree[c].m+1, r);
    }
    merge(c);
    return L+R;
}

int main(){
    scanf("%d", &T);
    while(T--){
        scanf("%d%d", &n, &c);
        build(1,1, n);
        for(int i=0; i<c;i++){
            scanf("%d%d%d", &t,&p,&q);

            if(!t) scanf("%d", &v);
            if(!t) update(1,p,q,v);
            else printf("%I64d\n", query(1,p,q));
        }

    }
    return 0;
}

ACM_kirakira

2015年5月11日星期一

Segment Tree + BIT (Fenwick Tree) In Deep

Segment Tree + BIT (Fenwick Tree) In Deep

BIT (Fenwick Tree) Part

Segment Tree Part

沒有留言:

張貼留言

2015年5月11日 星期一

Segment Tree + BIT (Fenwick Tree) In Deep

Segment Tree + BIT (Fenwick Tree) In Deep

BIT (Fenwick Tree) Part

Segment Tree Part

沒有留言:

張貼留言

2015年5月11日星期一