動機

為什麼能倍增?

將2的次冪排成一個序列，即1,2,4,8,16,32……在這個序列中取任意個不相等的數，相加可以得到所有正整數

Sparse Table

定義st[i][j] => [i, i+2^j -1]這是閉區間

之後把這個range二分，[i, i+2^(j-1)-1] [i+2^(j-1), i+2^(j-1)-1] st[i][j] = st[i][j-1] + st[i+2^(j-1)][j-1]

from math import log2

def make_st(arr):
  st = {}
  K = log2(len(arr))

  for i,n in enumerate(arr):
    st[(i, 0)] = n
  
  for j in range(1,K+1):
    for i in filter(lambda i: i+(1 << j) <= len(arr), range(len(arr))):
      st[(i,j)] = st[(i, j-1)] + st[(i+(1 << (j-1)), j-1)]
  
  return [K, st]

只要是有結合律的函數(+, min, max)都可以用ST或是線段樹，之類可以作區間操作的DS

LCA

定義grand[i][j]為節點i高2^j個level的祖先

那這要怎麼遞迴定義? 二分 所以用2^j-1去分，所以先跳到2^j-1，再往上跳2^j-1

grand[i][j] = grand[grand[i][j-1]][j-1]

from collections import defaultdict
from math import log2, ceil

def build(tree):
    grand = defaultdict(lambda x: None)
    dep = defaultdict(int)
    dep[None] = -1
    def dfs(root, parent=None):
        if root:
            grand[(root, 0)] = parent
            dep[root] += dep[parent]+1
            j = 1
            while (1 << j) <= dep[root]:
                grand[(root, j)] = grand[(grand[(root,j-1)], j-1)]
                j += 1
            dfs(root.left)
            dfs(root.right)
    dfs(tree)
    return [dep, grand]

之後的查詢就是

  1. 先把兩個調到一樣高
  2. 從最大的2次方去試，直到兩邊相遇
dep, grand = build(tree)
def lca(a, b):
    if dep[b] < dep[a]:
        return lca(b, a)
    else:
        K = ceil(log2(len(dep.keys())))
        for j in reversed(range(K+1)):
            if dep[b]-(1 << j) >= dep[a]:
                b = grand[(b, j)]
        
        if a is b:
            return a
        else:
            for j in reversed(range(K+1)):
                if grand[(b, j)] is not grand[(a, j)]:
                    a, b = grand[(a, j)], grand[(b, j)]
            return grand[(a, 0)]

Ref

sparse-table LCA问题（倍增法）