数状数组-理解总结

[ZhangCheng-zh]

适用范围

点状修改，区间查询

LOWBIT

private int lowbit(int x) {
    return x & (-x);
}

实际上其主要功能是: 找到x的二进制数的最后一个1所表示的二进制 注意: x不能等于0, 否则会进入死循环, 所以树状数组通常使用的下标会执行+1操作

定义树状数组

首先定义一个累加和数组 sumssums , 假设数组有8个元素,如图所示,其中ni是原始数据, si是累加和数据

更新\查询树状数组

• 更新树状数组时使用 x += lowBit(x) 来寻找被影响的数组下标

• 查询树状数组时使用 x -= lowBit(x)来寻找小于x的下一个区间

Example:Range Sum Query

class NumArray {
    constructor(nums: number[]) {
        this.nums = nums
        this.n = nums.length
        this.tree = new Array(this.n + 1).fill(0)
        for (let i = 0; i < this.n; i++) {
            this.add(i + 1, this.nums[i])
        }
    }
    nums: number[]
    tree: number[]
    n: number

    lowbit(x) {
        return x & -x
    }

    add(x: number, v: number): void {
        for (let i = x; i <= this.n; i += this.lowbit(i)) this.tree[i] += v
    }

    query(x: number): number {
        let ans = 0
        for (let i = x; i > 0; i -= this.lowbit(i)) ans += this.tree[i]
        return ans
    }

    update(index: number, val: number): void {
        this.add(index + 1, val - this.nums[index])
        this.nums[index] = val
    }

    sumRange(left: number, right: number): number {
        return this.query(right + 1) - this.query(left)
    }
}