blob: dd6bfdbef587e7400a4f07c4f0f455121555b5b2 (
plain)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
|
package corpus
type fenwikTree struct {
array []int64
data []int64
fullSum int64
size int
capacity int
}
func (t *fenwikTree) addNew(val int64) {
if t.size+1 >= t.capacity {
t.extendAndRebuild()
}
t.size++
t.add(t.size, val)
}
func (t *fenwikTree) add(ind int, val int64) {
t.fullSum += val
t.array[ind] += val
for ind < t.capacity {
t.data[ind] += val
ind += ind & -ind
}
}
func (t *fenwikTree) get(ind int) int64 {
return t.array[ind]
}
func (t *fenwikTree) set(ind int, val int64) {
t.add(ind, val-t.get(ind))
}
func (t *fenwikTree) prefixSumTo(ind int) (sum int64) {
for ind > 0 {
sum += t.data[ind]
ind -= ind & -ind
}
return
}
func (t *fenwikTree) reserve(cap int) {
t.capacity = cap
t.extendAndRebuild()
}
func (t *fenwikTree) extendAndRebuild() {
if t.capacity == 0 {
t.capacity = 16
} else {
t.capacity *= 2
}
oldArray := t.array
t.array = make([]int64, t.capacity)
t.data = make([]int64, t.capacity)
t.fullSum = 0
for i := 1; i < len(oldArray); i++ {
t.add(i, oldArray[i])
}
}
|
