树状数组/二叉索引树(Binary Indexed Tree)

• 树状数组：用数组来模拟树形结构。
• 应用：解决大部分基于区间上的更新以及求和（区间和）问题。
• 时间复杂度：查询 O(log(n))、修改 O(log(n))。
• 空间复杂度：O(log(n))。

参考

• https://oi-wiki.org/ds/fenwick/
• https://www.cnblogs.com/xenny/p/9739600.html
• https://www.cnblogs.com/findview/archive/2019/08/01/11281628.html
• https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solution/shu-zhuang-shu-zu-by-liweiwei1419/
• https://leetcode.cn/problems/count-of-smaller-numbers-after-self/solution/yi-wen-zhang-wo-shu-zhuang-shu-zu-by-a-fei-8/

0、定义

• 离散化优化空间：把原序列的值域映射到一个连续的整数区间，并保证它们的偏序关系不变。

1、操作

• 3个函数
• 1、单点修改：upData(i, k int)
• 2、区间查询：getSum(i int)
• 3、获取位：lowBit(i int) 返回参数转为二进制后,最后一个1的位置所代表的数值。 算出x二进制的从右往左出现第一个1以及这个1之后的那些0组成数的二进制对应的十进制的数

2、实现

package main

import "fmt"

func main() {
    arr := []int{1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 10, 9, 8, 7, 6, 5, 4, 3, 2, 1}
    n := len(arr)
    c = make([]int, n+1)
    length = n
    for i := 0; i < n; i++ {
        upData(arr[i], 1)
    }
    for i := 0; i < n; i++ {
        fmt.Println(i, getSum(i))
    }
}

var length int
var c []int // 树状数组

// 取2^k：2^k = i&(-i)
// x&(-x)，
// x为0时结果为0；
// x为奇数时，结果为1；
// x为偶数时，结果为x中2的最大次方的因子。
func lowBit(x int) int {
    return x & (-x)
}

// 单点修改
func upData(i, k int) { // 在i位置加上k
    for i <= length {
        c[i] = c[i] + k
        i = i + lowBit(i) // i = i + 2^k
    }
}

// 区间查询
func getSum(i int) int {
    res := 0
    for i > 0 {
        res = res + c[i]
        i = i - lowBit(i)
    }
    return res
}

3、Leetcode