Binary Indexed Tree

 1type binaryIndexedTree []int
 2
 3func newBinaryIndexedTree(n int) *binaryIndexedTree {
 4	bit := make(binaryIndexedTree, n+1)
 5	return &bit
 6}
 7
 8func (t binaryIndexedTree) Sum(i int) int {
 9	s := 0
10	for i++; i > 0; i -= i & -i {
11		s += t[i]
12	}
13	return s
14}
15
16func (t binaryIndexedTree) RangeSum(l, r int) int {
17	return t.Sum(r-1) - t.Sum(l-1)
18}
19
20func (t binaryIndexedTree) Add(i, x int) {
21	for i++; i < len(t) && i > 0; i += i & -i {
22		t[i] += x
23	}
24}
25
26func (t binaryIndexedTree) LowerBound(x int) int {
27	idx, k := 0, 1
28	for k < len(t) {
29		k <<= 1
30	}
31	for k >>= 1; k > 0; k >>= 1 {
32		if idx+k < len(t) && t[idx+k] < x {
33			x -= t[idx+k]
34			idx += k
35		}
36	}
37	return idx
38}
39