三个月算法进阶--day80

2020-11-11 约 282 字预计阅读 1 分钟次阅读

补码

负数的补码：负数的绝对值按位取反再＋1

计算机中数值用补码存储

按位取反2 ^ n - 1 - x，补码即2 ^ n - x，对2 ^ n取模之后的-x

减去一个数等于加上一个数的补码

n & -n = x ^ k，k为n从右往左连续0的个数（0除外）

lowbit(7) = 1 lowbit(6) = 2 lowbit(4) = 4

把区间[1, n]划分成log n个小区间，[1, 4], [4+1, 2^2+2^1], [6+1, 2^2+2^1+2^0]，右边界索引对应的值为区间和

上图参考文章树状数组

查询前缀和

def query(x):
    ans = 0
    while x:
        ans += bit[x]
        x -= x & -x

单点增加，父节点的索引值 = 子节点索引值 + 其低位：parent(i) = i + lowbit(i)

def update(x, delta):
    while x < n:
        bit[x] += delta
        x += x & -x