Range Sum Query - Mutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.
The update(i, val) function modifies nums by updating the element at index i to val.
Example:
Given nums = [1, 3, 5]
sumRange(0, 2) -> 9
update(1, 2)
sumRange(0, 2) -> 8
Note:
The array is only modifiable by the update function.
You may assume the number of calls to update and sumRange function is distributed evenly.
この問題はRange Sum Query-Immutableという問題に比べてupdateメソッドが1つ増えているので,sumを事前に計算することで演算速度を向上させることはできない.ここでは、この問題を解決するための新しいデータ構造(Binary Indexed tree)を紹介します.ここでは、ツリー配列を構築する方法について簡単に説明します.
1つの配列nums[]が与えられたと仮定します.sumRangeメソッドでは、1つの要素を任意に変更するためにupdateメソッドが使用されます.次に、ツリー配列BIT[]を構築します.いずれかの要素BIT[i]は、1つまたは複数のnums配列の要素の和である可能性があります.BIT[i]の決定方法含まれる要素は、ここではビット演算の知識で処理します.iのバイナリ表現にkビット連続の0があると仮定すると、配列numsの下にiより小さい前の2^k個の要素の和になります.
注*BIT配列を構築する場合、BIT[0]=0で空を表します.
例:
BIT[1]=nums[0](1のバイナリ表現は0001、k=0、2^k=1であるためnums[0]のみを含む.
BIT[2]=nums[0]+nums[1](2=0010,k=1,2^k=2であるため、前の2つの要素を含む).
BIT[3]=nums[2](3=0011,k=0,2^k=1であるため、3に隣接して3よりも小さい要素nums[2]のみが含まれる.
BITを構築すると、この問題は解決され、時間の複雑さはO(logn)であり、コードは以下の通りである.

public class NumArray {
    int[] nums;
    int[] BIT;
    
    public NumArray(int[] nums) {
        this.nums = nums;
        BIT = new int[nums.length + 1];
        for(int i = 0; i < nums.length; i++) {
            init(i, nums[i]);
        }
    }
    public void init(int i, int val) {
        i ++;
        while(i <= nums.length) {
            BIT[i] += val;
            i += (i & -i);
        }
    }
    void update(int i, int val) {
        int differ = val - nums[i];
        nums[i] = val;
        init(i, differ);
    }
    public int getSum(int i) {
        i ++;
        int sum = 0;
        while(i > 0) {
            sum += BIT[i];
            i -= (i & -i);
        }
        return sum;
    }
    public int sumRange(int i, int j) {
        return getSum(j) - getSum(i - 1);
    }
}


// Your NumArray object will be instantiated and called as such:
// NumArray numArray = new NumArray(nums);
// numArray.sumRange(0, 1);
// numArray.update(1, 10);
// numArray.sumRange(1, 2);