# 110 選手班 - 基礎資結 ###### tags: `宜中資訊` `CP` Ccucumber12 2020.08.06 --- ## Outline - Binary heap - DSU - Sparse table - Fenwick tree - Segment tree --- ## Binary Heap ---- ### Function - Insert - Query Max/Min - Pop Max/Min ---- ### Structure - Complete binary tree - Father $\geq$ Child - Root is max/min - Array implement ----  ---- ### Insert - insert at the lowest leaf - adjust upwards - $O(log\ N)$ ---- ### Pop - swap root and lowest leaf - delete lowest leaf - adjust downwards - $O(log\ N)$ ---- ### Implementation ```c= const int INF = 0x3f3f3f3f ; int hp[2000010] ; int e = 0 ; void init() { for(int i=1; i<=100000; ++i) hp[i] = -INF ; } void insert(int x) { e++ ; hp[e] = x ; int tmp = e ; // current index while(tmp > 1 && hp[tmp] > hp[tmp / 2]) { swap(hp[tmp], hp[tmp/2]) ; tmp /= 2 ; } } void pop() { swap(hp[1], hp[e]) ; hp[e] = -INF ; e-- ; int tmp = 1 ; while(hp[tmp] < max(hp[tmp * 2], hp[tmp * 2 + 1])) { int l = tmp * 2, r = tmp * 2 + 1 ; if(hp[l] > hp[r]) { swap(hp[tmp], hp[l]) ; tmp = l ; } else { swap(hp[tmp], hp[r]) ; tmp = r ; } } } ``` --- ## Disjoint Set Union ---- ### Function - query set's index - query if same set - unite two sets ---- ### Structure - Tree / Forest - father is itself: root - set index: root - Array Implement ----  ---- ### Initialize - Every index is independent - Let every index point to themselves - $O(N)$ ---- ### Find - Find the root of current index - Recursive until root - Shorten the path - $O(\alpha(N))$ ---- ### Unite - Combine two sets - Let one root's father := the other root - Modify the smaller group - $O(\alpha(N))$ ---- ### Query - query if two index is same set - use find() - $O(\alpha(N))$ ---- ### Implementation ```c= int dsu[100010] ; void init() { for(int i=0; i<=100000; ++i) dsu[i] = i ; } int find(int x) { return dsu[x] == x ? x : dsu[x] = find(dsu[x]) ; } void unite(int x, int y) { dsu[find(y)] = find(x) ; } ``` --- ## Sparse Table ---- ### Function - Static RMQ - O(1) Query ---- ### RMQ - Range Minimum/Maximum Query - Sum, Multiplication, GCD, XOR, ... - Static / Dynamic ---- ### Structure - $(N) \times (log\ N)$ table - $spt[i][j]\ :=\ min[i,\ i + 2^j-1]$ ----  ---- ### Build - $spt[i][j]\ :=\ min[i,\ i + 2^j - 1]$ - $spt[i][0] = a[i]$ - $spt[i][j+1] = min(spt[i][j],\ spt[i+2^j][j])$ ---- - DP - $O(Nlog\ N)$ ---- ### Query - $lg\ :=\ log\lfloor r-l+1\rfloor$ - query(l, r) = $min(spt[l][lg], spt[r - 2^{lg}+1][lg])$ - $O(1)$ ---- ### Implementation ```c= int a[100010] ; int spt[200010][30] ; void build(int n) { for(int i=1; i<=n; ++i) { spt[i][0] = a[i] ; } for(int i=1; i<=log2(n); ++i) { for(int j=1; j<=n; ++j) { spt[j][i] = max(spt[j][i-1], spt[j + (1 << (i-1))][i-1]) ; } } } int query(int l, int r) { int lg = log2(r - l + 1) ; return min(spt[l][lg], spt[r - (1<<lg) + 1][lg]) ; } ``` ---- ### KEY - +1 / -1 - query minimum $\rightarrow$ initialize - boudaries (RE) --- ## Fenwick Tree ---- ### Names - Fenwick Tree - Binary Indexed Tree - 樹狀陣列 - 二元索引樹 - BIT ---- ### Function - Range Sum Query - add value ---- ### Structure - (Half) Perfect Binary Tree - $bt[i] = sum[i - lowbit(i) + 1,\ i]$ ---- ### Lowbit - LSB(Least Significant Bit) - $12 = 1100_{(2)} \rightarrow lowbit(12) = 100_{(2)} = 4$ - $8 = 1000_{(2)} \rightarrow lowbit(8) = 1000_{(2)} = 8$ ---- - `lowbit(x) = (x&-x)` - $12 = ...001100_{(2)}$ - $-12 = ...110100_{(2)}$ - $12\ \&-12 = ...000100_{(2)}$ ----  ----  ---- ### Add - add $k$ to index $x$ - modify every range include $x$ - enumerate through adding lowbit - $O(log\ N)$ ---- ### Query - Query $sum[1, x]$ - add different ranges to sum up $[1,x]$ - enumerate through subtracting lowbig - $O(log\ N)$ ---- ### Implementation ```c= int bt[100010] ; int n ; void add(int x, int k) { for(int i=x; i<=n; i += (i&-i)) { bt[i] += k ; } } void add(int x, int y, int k) { for(int i=x; i<=n; i+=(i&-i)) for(int j=y; j<=n; j+=(i&-j)) bt[i][j] = k ; } int query(int x) { int ret = 0 ; for(int i=x; i>0; i -= (i&-i)) { ret += bt[i] ; } return ret ; } int sum(int l, int r) { return query(r) - query(l - 1) ; } ``` ---- ### Advance - XOR - monotonic Max / Min - 2D BIT --- ## Segment Tree ---- ### Function - Range Min/Max/Sum Query - Modify value ---- ### Structure - Perfect Binary Tree - combine adjacent ranges every new layer - $O(N) \times O(log\ N)$ size ----  ---- ### Build - make length into power of two - recursive - $[L, R] = f([L,mid],\ [mid+1,R])$ - $O(N)$ ---- ### Modify - modify index $x$ to $k$ - adjust every ancestor of $x$ - going up by dividing two - $O(log\ N)$ ---- ### Query - Query $f[l, r]$ - start from $[1,N]$ - recursive $[Lb, Rb] = f([Lb, mid],\ [mid+1,Rb])$ - $O(log\ N)$ ---- ### Implementation ```c= int N, MXN ; int seg[4000010] ; // 4 * N void build(int lb, int rb, int idx) { if(lb == rb) return ; int mid = (lb + rb) / 2 ; build(lb, mid, idx*2) ; build(mid + 1, rb, idx*2+1) ; seg[idx] = seg[idx*2] + seg[idx*2+1] ; } void modify(int x, int k) { x = x + MXN - 1 ; seg[x] = k ; while(x > 1) { x /= 2 ; seg[x] = seg[x*2] + seg[x*2+1] ; } } int query(int l, int r, int lb, int rb, int idx) { if(l <= lb && rb <= r) { return seg[idx] ; } int mid = (lb + rb) / 2 ; int ret = 0 ; if(l <= mid) ret += query(l, r, lb, mid, idx*2) ; if(r >= mid+1) ret += query(l, r, mid+1, rb, idx*2+1) ; return ret ; } int main() { int a[100010] ; cin >> N ; MXN = 1 ; while(MXN < N) MXN <<= 1 ; for(int i=1; i<=N; ++i) seg[MXN + i - 1] = a[i] ; build(1, MXN, 1) ; } ``` ---- ### Advance - Lazy Tag - Range Modify - GCD, XOR - D&Q --- ## Credit - https://helloacm.com/disjoint-sets/ - https://hackmd.io/@Lssh-Algorithm/S1fUmuUJ_ - https://www.youtube.com/watch?v=uUatD9AudXo - Sprout - OI wiki