树状数组

Binary Indexed Tree

1649. 通过指令创建有序数组 5999. 统计数组中好三元组数目 2426. 满足不等式的数对数目 493. 翻转对剑指 Offer 51. 数组中的逆序对

TypeScript

export function useBIT(nums: number[]) {
    const lowbit = (x: number) => x & -x

    const n = nums.length
    const tree = new Array(n + 1).fill(0)

    for (let i = 0; i < n; i++) add(i, nums[i])

    function add(idx: number, val: number) {
        for (let i = idx + 1; i <= n; i += lowbit(i)) tree[i] += val
    }

    function update(idx: number, val: number) {
        add(idx, val - nums[idx])
    }

    function query(idx: number) {
        let res = 0
        for (let i = idx + 1; i > 0; i -= lowbit(i)) res += tree[i]
        return res
    }

    function queryByInterval(left: number, right: number) {
        return query(right) - query(left - 1)
    }

    return {
        add,
        update,
        query,
        queryByInterval,
    }
}

JavaScript

export function useBIT(nums) {
    const lowbit = (x) => x & -x
    const n = nums.length
    const tree = new Array(n + 1).fill(0)
    for (let i = 0; i < n; i++) add(i, nums[i])
    function add(idx, val) {
        for (let i = idx + 1; i <= n; i += lowbit(i)) tree[i] += val
    }
    function update(idx, val) {
        add(idx, val - nums[idx])
    }
    function query(idx) {
        let res = 0
        for (let i = idx + 1; i > 0; i -= lowbit(i)) res += tree[i]
        return res
    }
    function queryByInterval(left, right) {
        return query(right) - query(left - 1)
    }
    return {
        add,
        update,
        query,
        queryByInterval,
    }
}

Rust

pub struct BIT {
    n: usize,
    tree: Vec<i64>,
}

impl BIT {
    pub fn new(n: usize) -> Self {
        BIT {
            n,
            tree: vec![0; n + 1],
        }
    }

    pub fn add(&mut self, i: usize, x: i64) {
        let mut i = i + 1;
        while i <= self.n {
            self.tree[i] += x;
            i += i & i.wrapping_neg();
        }
    }

    pub fn query(&self, i: usize) -> i64 {
        let mut s = 0;
        let mut i = i + 1;
        while i > 0 {
            s += self.tree[i];
            i -= i & i.wrapping_neg();
        }
        s
    }
}

Java


class BinaryIndexedTree {

    int[] tree, nums;
    int n;

    public BinaryIndexedTree(int[] nums) {
        n = nums.length;
        this.nums = nums;
        // tree 下标以 1 开始
        tree = new int[n + 1];
        for (int i = 0; i < n; i++) {
            add(i, nums[i]);
        }
    }

    /**
     * 在指定下标增加值
     *
     * @param idx 指定数组下标
     * @param val 要增加的值（不是修改，是增加）
     */
    public final void add(int idx, int val) {
        for (int i = idx + 1; i <= n; i += lowbit(i)) {
            tree[i] += val;
        }
    }

    /**
     * 更新指定下标的值
     *
     * @param idx 指定数组下标
     * @param val 要更新的值
     */
    public void update(int idx, int val) {
        add(idx, val - nums[idx]);
        nums[idx] = val;
    }

    /**
     * 查找前缀和
     *
     * @param idx 查询的右端点
     * @return nums[0:idx] 的和
     */
    public int query(int idx) {
        int res = 0;
        for (int i = idx + 1; i > 0; i -= lowbit(i)) {
            res += tree[i];
        }
        return res;
    }

    /**
     * 查询[left, right]区间和
     *
     * @param left  左端点（闭）
     * @param right 右端点（闭）
     */
    public int query(int left, int right) {
        return query(right) - query(left - 1);
    }

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