Region and retrieval–array can be modified

line segment tree

• Reference link

code

class NumArray {

 private ArrayList sumSegmentTree;

 private int n;



 public NumArray(int[] nums) {

 n = nums.length;

 sumSegmentTree = new ArrayList<>(2 * n + 1);

 for (int i = 0; i  sumSegmentTree.add(0);

}



 for (int i = 0; i  sumSegmentTree.add(nums[i]);

}



 for (int i = n-1; i> 0; i--) {

 sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));

}

}



 public void update(int i, int val) {

 i += n;

 sumSegmentTree.set(i, val);

 while (i> 1) {

 i /= 2;

 sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));

}

}



 /** The original algorithm is described as range[left,right)

 * range[i,j]

 * @param i left subscript

 * @param j subscript right

 * @return sum

 */

 public int sumRange(int i, int j) {

 int sum = 0;

 i += n;

 j += n+1;

 while (i  if ((i & 1) == 1) {

 sum += sumSegmentTree.get(i);

 i ++;

}

 if ((j & 1) == 1) {

 j --;

 sum += sumSegmentTree.get(j);

}



 i >>= 1;

 j >>= 1;

}

 return sum;

}

}





/**

 * Your NumArray object will be instantiated and called as such:

 * NumArray obj = new NumArray(nums);

 * obj.update(i,val);

 * int param_2 = obj.sumRange(i,j);

 */

class NumArray {

 private ArrayList sumSegmentTree;

 private int n;



 public NumArray(int[] nums) {

 n = nums.length;

 sumSegmentTree = new ArrayList<>(2 * n + 1);

 for (int i = 0; i  sumSegmentTree.add(0);

}



 for (int i = 0; i  sumSegmentTree.add(nums[i]);

}



 for (int i = n-1; i> 0; i--) {

 sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));

}

}



 public void update(int i, int val) {

 i += n;

 sumSegmentTree.set(i, val);

 while (i> 1) {

 i /= 2;

 sumSegmentTree.set(i, sumSegmentTree.get(2 * i) + sumSegmentTree.get(2 * i + 1));

}

}



 /** The original algorithm is described as range[left,right)

 * range[i,j]

 * @param i left subscript

 * @param j subscript right

 * @return sum

 */

 public int sumRange(int i, int j) {

 int sum = 0;

 i += n;

 j += n+1;

 while (i  if ((i & 1) == 1) {

 sum += sumSegmentTree.get(i);

 i ++;

}

 if ((j & 1) == 1) {

 j --;

 sum += sumSegmentTree.get(j);

}



 i >>= 1;

 j >>= 1;

}

 return sum;

}

}





/**

 * Your NumArray object will be instantiated and called as such:

 * NumArray obj = new NumArray(nums);

 * obj.update(i,val);

 * int param_2 = obj.sumRange(i,j);

 */