Skip to content

Instantly share code, notes, and snippets.

@kooooohe
Created April 27, 2021 16:42
Show Gist options
  • Save kooooohe/59424955a116c1e4e48d82ece94330e6 to your computer and use it in GitHub Desktop.
Save kooooohe/59424955a116c1e4e48d82ece94330e6 to your computer and use it in GitHub Desktop.
ap blog
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{4, 2, 1, 5, 8, 6, 3, 7}
b := NewBIT(len(t))
ans:=0
for i, v := range t {
ans += i-b.Sum(v)
b.Add(v, 1)
b.Debug()
}
fmt.Println(ans)
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment