在力扣上刷题时，遇到非常有意思的一种数据结构，可以方便计算前缀和的同时，还可以进行单点更新。它就是树状数组。

在网上并没有搜索到太多树状数组的 JavaScript 相关代码，所以在这里自己动手实现一个树状数组类。

/**
 * 树状数组类
 */
class BinaryIndexedTree {
    tree = []
    n = 0
    /**
     * 树状数组构造函数
     * @param n 树状数组长度
     */
    constructor(n) {
        this.n = n
        this.tree = new Array(n + 1).fill(0)
    }

    // 计算低位
    static lowbit (x) {
        return x & (-x)
    }

    // 查询
    query (x) {
        let res = 0
        while (x !== 0) {
            res += this.tree[x]
            x -= BinaryIndexedTree.lowbit(x)
        }
        return res
    }

    // 更新，在 x 位置上的值加 v
    update (x, v) {
        while (x <= this.n) {
            this.tree[x] += v
            x += BinaryIndexedTree.lowbit(x)
        }
    }
}