動機

記錄用

分塊

通過對原數據的適當劃分，並在劃分後的每一個塊上預處理部分信息(像是sum，還可以附加訊息，像是懶標)，從而較一般的暴力算法取得更優的時間複雜度。

分塊的時間複雜度主要取決於分塊的塊長，一般可以通過均值不等式求出某個問題下的最優塊長，以及相應的時間複雜度。

Sqrt Decomposition

每一格用根號長度去分組，這樣q次query的整體複雜度就是O(n+q*sqrt(n))

為什麼是根號? 一次query要花O(n/size + size)，n/size是走了幾個完整的塊，size是剩下的item

而這與算幾不等式很像，所以要讓n/size = size，那size就是根號

算幾不等式

tmp = n/size

(tmp+size) / 2 >= sqrt(tmp*size)

def sqrt_decomposition(arr):
  import math

  ret = []
  size = math.floor(math.sqrt(len(arr)))
  for i,n in enumerate(arr):
    if len(ret) <= i//size:
      ret.append(0)
    ret[-1] += n
  return [ret, size]

b, size = sqrt_decomposition(arr)
def answer(i,j):
  b_i, b_j = i//size, j//size

  if b_i == b_j: # 在同一區
    return sum(arr[i:j])
  else:
    # i ... b_i_end b_i+1_start b_i+1_end ... b_i+2_start ...... b_j_start ... j
    # b_i*size+size: b_i*size還是在 i 所在的區域，所以再加一個size，跳到下一格
    return sum(arr[i:(b_i*size+size)])+sum(b[b_i+1:b_j])+sum(arr[b_j*size:j])

TODO: Mo’s algorithm

bucket sort

把數字分到各個桶子中

def bucket(arr):
    but = [[] for _ in range(min(arr), max(arr))]
    [but[n-min(arr)].append(n) for n in arr]
    ret = []
    for i in range(len(but)):
        [ret.append(x) for x in but[i] if but[i]]
    return ret

worst time comp: O(讀len(arr)元素^2) (如果全部都在同一個bucket，並用insert sort去sort bucket的元素) avg time comp: O(讀len(arr)元素 + bucket的長度)

現在是一個數字對到一個index，但事實上可以讓一個range的數字對到一個index，這樣就有趣了

counting sort

  1. 計數
  2. 算prefix sum，就是看這個數字要有前面已經被占了多少格
  3. 開始放，放完就在原本的prefix sum上加一
def counting(arr):
    cnts = [0 for _ in range(min(arr), max(arr))]
    # count
    for n in arr:
        cnts[n-min(arr)] += 1
    # prefix sum
    for i in range(1,len(cnts)):
        cnts[i] += cnts[i-1]
    # place each element
    ret = list(arr)
    for n in arr:
        ret[n-min(arr)] = cnts[n-min(arr)]
        cnts[n-min(arr)] += 1
    return ret

time comp: O(讀len(arr)元素 + prefix sum的長度)

radix sort

每次用一個位數digit去sort，如果位數不存在就當0，sort到最後就是radix sort

有趣的是，如果從最右邊(LSM，最小位數)開始走就是一般的sort，但如果從最左邊(MSM，最大位數)開始走就變成字典序!! 126與8

time comp: O(幾個位數 * O(counting sort))

Ref

分塊法 分块思想 Sqrt Decomposition