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
|
package main
import (
"database/sql"
)
type segmentTree struct {
N int
seg []int
}
// Build segment tree
func (s *segmentTree) Build(a *sql.Rows, l, r, n int) {
if l == r {
a.Next()
a.Scan(&s.seg[n])
return
}
m := (l + r) >> 1
s.Build(a, l, m, n<<1)
s.Build(a, m+1, r, n<<1|1)
s.seg[n] = s.seg[n<<1] + s.seg[n<<1|1]
}
// Update value at index x
func (s *segmentTree) Update(x, v, l, r, n int) {
if l == r {
s.seg[n] = v
return
}
m := (l + r) >> 1
if x <= m {
s.Update(x, v, l, m, n<<1)
} else {
s.Update(x, v, m+1, r, n<<1|1)
}
s.seg[n] = s.seg[n<<1] + s.seg[n<<1|1]
}
// Find element with prefix sum v
func (s *segmentTree) Query(v, l, r, n int) (int, int) {
if l == r {
return s.seg[n], l
}
m := (l + r) >> 1
if s.seg[n<<1] >= v {
return s.Query(v, l, m, n<<1)
} else {
return s.Query(v-s.seg[n<<1], m+1, r, n<<1|1)
}
}
|
