Size Balance Tree vs Segment Tree

假設想有一個data structure, 想support:

1. add(x)
2. rank(x)
3. delete(x)

在O(log N)時間內做到

做法可以用陳XX的Size Balance Tree, 不過個人覺得code很長, 在爭分奪秒的ACM上, 用 segment tree 代替可能更好

先把所有 data discretize
(不過可能就要store起所有query.. um..)

揼個 segment tree, 每個 node store sum = left subtree's sum + right subtree's sum
leaf's sum initialize = 0

每次add(x) 就把對應的 leaf set 做 1
delete(x) 就 set 做 0
rank(x) 就在途中加起 left subtree 的 sum