@@ -0,0 +1,2177 @@
+package com.freetymekiyan.algorithms.level.medium;%0A%0Aimport org.junit.Test;%0A%0A/**%0A * Given an integer array nums, find the sum of the elements between indices i and j (i %E2%89%A4 j), inclusive.%0A * %3Cp%3E%0A * The update(i, val) function modifies nums by updating the element at index i to val.%0A * %3Cp%3E%0A * Example:%0A * Given nums = %5B1, 3, 5%5D%0A * %3Cp%3E%0A * sumRange(0, 2) -%3E 9%0A * update(1, 2)%0A * sumRange(0, 2) -%3E 8%0A * Note:%0A * The array is only modifiable by the update function.%0A * You may assume the number of calls to update and sumRange function is distributed evenly.%0A * %3Cp%3E%0A * Tags: Segment Tree, Binary Indexed Tree%0A * Similar Problems: (E) Range Sum Query - Immutable, (H) Range Sum Query 2D - Mutable%0A */%0Apublic class RangeSumQueryMutable %7B%0A%0A    public class NumArray %7B%0A%0A        private final int%5B%5D nums;%0A        private final int%5B%5D BiTree;%0A        private final int n;%0A%0A        public NumArray(int%5B%5D nums) %7B%0A            this.nums = nums;%0A            n = nums.length;%0A            BiTree = new int%5Bn + 1%5D;%0A            for (int i = 0; i %3C n; i++) %7B%0A                init(i, nums%5Bi%5D);%0A            %7D%0A        %7D%0A%0A        private void init(int i, int val) %7B%0A            i++;%0A            while (i %3C= n) %7B%0A                BiTree%5Bi%5D += val;%0A                i += (i & -i);%0A            %7D%0A        %7D%0A%0A        void update(int i, int val) %7B%0A            int diff = val - nums%5Bi%5D;%0A            nums%5Bi%5D = val;%0A            init(i, diff);%0A        %7D%0A%0A        private int getSum(int i) %7B%0A            i++;%0A            int sum = 0;%0A            while (i %3E 0) %7B%0A                sum += BiTree%5Bi%5D;%0A                i -= (i & -i);%0A            %7D%0A            return sum;%0A        %7D%0A%0A        public int sumRange(int i, int j) %7B%0A            return getSum(j) - getSum(i - 1);%0A        %7D%0A    %7D%0A%0A// Your NumArray object will be instantiated and called as such:%0A// NumArray numArray = new NumArray(nums);%0A// numArray.sumRange(0, 1);%0A// numArray.update(1, 10);%0A// numArray.sumRange(1, 2);%0A%0A%0A    @Test%0A    public void testExamples() %7B%0A        int%5B%5D input = %7B1, 3, 5%7D;%0A        NumArray n = new NumArray(input);%0A        System.out.println(n.sumRange(0, 2));%0A        n.update(1, 2);%0A        System.out.println(n.sumRange(0, 2));%0A    %7D%0A%7D%0A

add Range Sum Query Mutable