Binary Index Tree solution


  • 0
    F

    This solution is not better than top votes solution, but it is easier to come up.
    I think best votes solution can drive from this solution.

    public int[] getModifiedArrayBinaryTree(int length, int[][] updates) {
            if (length == 0) return new int[0];
            int[] root = new int[length];
            for (int[] update: updates) {
                updateTree(root, update[1]+1, update[2]);
                updateTree(root, update[0], -update[2]);
            }
            for (int i = 0; i < length; i++) {
                root[i] = getValue(root, i+1, length);
            }
            return root;
        }
        
        private void updateTree(int[] root, int i, int value){
            while (i > 0) {
                root[i-1] += value;
                i -= (i&(-i));
            }
        }
        
        private int getValue(int[] root, int i, int n) {
            int res = 0;
            while (i <= n) {
                res += root[i-1];
                i += (i&(-i));
            }
            return res;
        }

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.