package leetcode;

/**
 * https://leetcode.com/problems/range-sum-query-mutable/
 */
public class Problem307 {
    public static class NumArray {

        public NumArray(int[] nums) {

        }

        void update(int i, int val) {

        }

        public int sumRange(int i, int j) {
            // TODO:
            return 0;
        }
    }

    public static void main(String[] args) {
        int[] nums = new int[]{1, 3, 5};
        NumArray numArray = new NumArray(nums);
        numArray.sumRange(0, 1);
        numArray.update(1, 10);
        numArray.sumRange(1, 2);
    }
}

@@ -143,97 +143,918 @@
 y %7B%0A
-%0A        public NumArray(int%5B%5D nums) %7B%0A%0A        %7D%0A%0A        void update(int i, int val) %7B%0A
+        private final int%5B%5D binaryIndexTree;%0A        private final int%5B%5D nums;%0A%0A        public NumArray(int%5B%5D nums) %7B%0A            // https://en.wikipedia.org/wiki/Fenwick_tree%0A            this.nums = new int%5Bnums.length%5D;%0A            binaryIndexTree = new int%5Bnums.length + 1%5D;%0A            for (int i = 0; i %3C nums.length; i++) %7B%0A                update(i, nums%5Bi%5D);%0A            %7D%0A        %7D%0A%0A        void update(int i, int val) %7B%0A            int delta = val - nums%5Bi%5D;%0A            nums%5Bi%5D = val;%0A            int idx = i + 1;%0A            while (idx %3C= nums.length) %7B%0A                binaryIndexTree%5Bidx%5D += delta;%0A                idx += idx & (-idx);%0A            %7D%0A        %7D%0A%0A        private int sum(int i) %7B%0A            int sum = 0;%0A            int idx = i + 1;%0A            while (idx %3E 0) %7B%0A                sum += binaryIndexTree%5Bidx%5D;%0A                idx -= idx & (-idx);%0A            %7D%0A            return sum;
 %0A   
@@ -1121,37 +1121,34 @@
     
-// TODO:%0A            return 0
+return sum(j) - sum(i - 1)
 ;%0A  
@@ -1242,15 +1242,42 @@
 t%5B%5D%7B
-1, 3, 5
+2, 1, 1, 3, 2, 3, 4, 5, 6, 7, 8, 9
 %7D;%0A 
@@ -1323,32 +1323,278 @@
 (nums);%0A        
+System.out.println(numArray.sum(2)); // 3%0A        numArray.update(1, 2);%0A        System.out.println(numArray.sum(2)); // 5%0A%0A//        int%5B%5D nums = new int%5B%5D%7B1, 3, 5%7D;%0A//        NumArray numArray = new NumArray(nums);%0A//        System.out.println(
 numArray.sumRang
@@ -1598,20 +1598,28 @@
 ange(0, 
-1);%0A
+2)); // 9%0A//
         
@@ -1641,21 +1641,22 @@
 (1, 
-10
+2
 );%0A
+//
         
 numA
@@ -1643,32 +1643,51 @@
 , 2);%0A//        
+System.out.println(
 numArray.sumRang
@@ -1688,22 +1688,28 @@
 umRange(
-1
+0
 , 2)
-;
+); // 8
 %0A    %7D%0A%7D

Solve problem 307