2D MRQ

J2DMrq.java

public class J2DMrq {

    private int n;
    private int[][] t = new int[0][0];
    private int m;

    public void build(int[][] arr) {
        n = arr.length;
        m = arr[0].length;
        t = new int[n << 2][m << 2];
        buildX(1, 0, n - 1, arr);
    }

    public int sum(int lx, int ly, int rx, int ry) {
        return sumQX(lx, ly, rx, ry, 1, 0, n - 1);
    }

    public void update(int x, int y, int value) {
        updateX(x, y, 1, 0, n - 1, value);
    }

    private void buildY(int vx, int lx, int rx, int vy, int ly, int ry, int[][] arr) {
        if (ly == ry) {
            if (lx == rx) {
                t[vx][vy] = arr[lx][ly];
            } else {
                t[vx][vy] = t[vx * 2][vy] + t[vx * 2 + 1][vy];
            }
        } else {
            int pivot = (ly + ry) / 2;
            buildY(vx, lx, rx, vy * 2, ly, pivot, arr);
            buildY(vx, lx, rx, vy * 2 + 1, pivot + 1, ry, arr);
            t[vx][vy] = t[vx][vy * 2] + t[vx][vy * 2 + 1];
        }
    }

    private void buildX(int v, int tl, int tr, int[][] arr) {
        if (tl != tr) {
            int pivot = (tl + tr) / 2;
            buildX(v * 2, tl, pivot, arr);
            buildX(v * 2 + 1, pivot + 1, tr, arr);
        }
        buildY(v, tl, tr, 1, 0, m - 1, arr);
    }

    private int sumQY(int vx, int ly, int ry, int vy, int vl, int vr) {
        if (ly > ry) {
            return 0;
        } else if (ly == vl && ry == vr) {
            return t[vx][vy];
        } else {
            int pivot = (vl + vr) / 2;
            int left = sumQY(vx, ly, Math.min(pivot, ry), vy * 2, vl, pivot);
            int right = sumQY(vx, Math.max(pivot + 1, ry), ry, vy * 2 + 1, pivot + 1, vr);
            return left + right;
        }
    }


    private int sumQX(int lx, int ly, int rx, int ry, int vx, int vl, int vr) {
        if (lx > rx) {
            return 0;
        } else if (lx == vl && rx == vr) {
            return sumQY(vx, ly, ry, 1, 0, m - 1);
        } else {
            int pivot = (vl + vr) / 2;
            int left = sumQX(lx, ly, Math.min(pivot, rx), ry, vx * 2, vl, pivot);
            int right = sumQX(Math.max(lx, pivot + 1), ly, rx, ry, vx * 2 + 1, pivot + 1, vr);
            return left + right;
        }
    }

    private void updateY(int x, int y, int lx, int rx, int vx, int vy, int vl, int vr, int value) {
        if (vl == vr) {
            if (lx == rx) {
                t[vx][vy] = value;
            } else {
                t[vx][vy] = t[vx * 2][vy] + t[vx * 2 + 1][vy];
            }
        } else {
            int pivot = (vl + vr) / 2;
            if (y <= pivot) {
                updateY(x, y, lx, rx, vx, vy * 2, vl, pivot, value);
            } else {
                updateY(x, y, lx, rx, vx, vy * 2 + 1, pivot + 1, vr, value);
            }
            t[vx][vy] = t[vx][vy * 2] + t[vx][vy * 2 + 1];
        }
    }

    private void updateX(int x, int y, int vx, int vl, int vr, int value) {
        if (vr != vl) {
            int pivot = (vl + vr) / 2;
            if (x <= pivot) {
                updateX(x, y, vx * 2, vl, pivot, value);
            } else {
                updateX(x, y, vx * 2 + 1, pivot + 1, vr, value);
            }
        }
        updateY(x, y, vl, vr, vx, 1, 0, m - 1, value);
    }

}