首页 > itarticle > binary indexed tree

binary indexed tree

admin 11月 13, 2020 0

A Fenwick tree or binary indexed tree is a data structure that can efficiently update elements and calculate prefix sums in a table of numbers.

1D

public class  {
    private int[] sum;

    public (int n) {
        sum = new int[n + 1];
    }

    public void update(int i, int delta) {
        while (i < sum.length) {
            sum[i] += delta;
            i += lowbit(i);
        }
    }

    public int query(int i) {
        int result = 0;

        while (i > 0) {
            result += sum[i];
            i -= lowbit(i);
        }

        return result;
    }

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

2D

public class  {
    private int[][] sum;

    public (int m, int n) {
        sum = new int[m + 1][n + 1];
    }

    public void update(int row, int col, int delta) {
        for (int i = row; i < sum.length; i += lowbit(i)) {
            for (int j = col; j < sum[0].length; j += lowbit(j))
                sum[i][j] += delta;
        }
    }

    public int query(int row, int col) {
        int result = 0;

        for (int i = row; i > 0; i -= lowbit(i)) {
            for (int j = col; j > 0; j -= lowbit(j))
                result += sum[i][j];
        }

        return result;
    }

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