Skip to content

Instantly share code, notes, and snippets.

@kooooohe
Created April 27, 2021 16:06
Show Gist options
  • Save kooooohe/d8ffbc5f54504c39f4bfcfb30be5e9ce to your computer and use it in GitHub Desktop.
Save kooooohe/d8ffbc5f54504c39f4bfcfb30be5e9ce to your computer and use it in GitHub Desktop.
blog ap
package main
import "fmt"
type BIT struct {
n int
bit []int
}
func (b *BIT) Sum(a int) int {
s := 0
for i := a; i > 0; i -= (i & -i) {
s += b.bit[i]
}
return s
}
func (b *BIT) Add(a, x int) {
for i := a; i < b.n; i += (i & -i) {
b.bit[i] += x
}
}
func (b *BIT) Debug() {
for _, v := range b.bit {
fmt.Print(v)
fmt.Print(" ")
}
fmt.Println()
}
func NewBIT(n int) *BIT {
return &BIT{n + 1, make([]int, n+1)}
}
func main() {
t := []int{1, 2, 4, 6, 1, 4, 6, 9}
b2 := NewBIT(len(t))
for i, v := range t {
b2.Add(i+1, v)
b2.Debug()
}
fmt.Println(b2.Sum(len(t)))
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment