［抄题］：
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
[暴力解法]：
时间分析：
空间分析：
[优化后]：
时间分析：
空间分析：
［奇葩输出条件］：
［奇葩corner case］：
- buildSegmentTree时，start > end，没有区间，不能build；相等时 求和直接赋值
- updateSegmentTree时，start == end，就只有一个点，该点值为val。
- 求sumRange时，表示到头了，可以直接返回root.sum。针对点来求和，参数应该是root的左右区间。
root.end == end && root.start == start
［思维问题］：
buildSegmentTree是基于数组的，sumRange是基于树的，所以都要新建函数 (函数名一样 参数不一样)
［英文数据结构或算法，为什么不用别的数据结构或算法］：
［一句话思路］：
从节点类开始，必须要有函数，把树新建起来
buildTree［输入量］：空： 正常情况：特大：特小：程序里处理到的特殊情况：异常情况（不合法不合理的输入）：
［画图］：
［一刷］：
- ret.sum要用左右节点的sum值更新 (通用的函数一般换一个名称 不直接用调用的名称)
ret.sum = ret.left.sum + ret.right.sum;
- update时，dc分为在左子树更新&在右子树更新
update(root.left, pos, val);
- 求和时，有三种情况。
［二刷］：
- root新建为空，buildtree的函数在外层
［三刷］：
- 树返回的是Node, 左右子树都要重建 不需要分类讨论
- update函数是根据插入位置pos和mid的关系来划分的 非左即右用的是if else
［四刷］：
［五刷］：
[五分钟肉眼debug的结果]：
［总结］：
［复杂度］：Time complexity: O(新建n 增加和删除是lgn) Space complexity: O(n)
［算法思想：迭代/递归/分治/贪心］：
分治
［关键模板化代码］：
［其他解法］：
［Follow Up］：
［LC给出的题目变变变］：
[代码风格] ：
[是否头一次写此类driver funcion的代码] ：
- public static void main (String[] args)方法在整个类里面
- root是动态变量，不能被当作静态值传输
// Java program to find largest rectangle with all 1s
// in a binary matrix
import java.io.*;
import java.util.*; class NumArray {
class segmentTreeNode{
int start, end;
segmentTreeNode left, right;
int sum; public segmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
this.left = null;
this.right = null;
this.sum = 0;
}
} //root
segmentTreeNode root = null; public NumArray(int[] nums) {
root = buildTree(nums, 0, nums.length - 1);
} public segmentTreeNode buildTree(int[] nums, int start, int end) {
//cc
if (start > end) return null;
else {
segmentTreeNode root = new segmentTreeNode(start, end);
if (start == end) root.sum = nums[start];
else {
int mid = start + (end - start) / 2;
root.left = buildTree(nums, start, mid);
root.right = buildTree(nums, mid + 1, end);
root.sum = root.left.sum + root.right.sum;
}
return root;
}
} public void update(int i, int val) {
update(root, i, val);
} public void update(segmentTreeNode root, int pos, int val) {
//cc change expression
if (root.start == root.end) root.sum = val;
else {
int mid = root.start + (root.end - root.start) / 2;
if (pos <= mid) {
update(root.left, pos, val);
}
else {
update(root.right, pos, val);
}
root.sum = root.left.sum + root.right.sum;
}
} public int sumRange(int i, int j) {
return sumRange(root, i, j);
} public int sumRange(segmentTreeNode root, int start, int end) {
//cc
if (root.start == start && root.end == end) return root.sum;
else {
int mid = root.start + (root.end - root.start) / 2;
if (end <= mid) return sumRange(root.left, start, end);
else if (start >= mid + 1) return sumRange(root.right, start, end);
else return sumRange(root.left, start, mid) + sumRange(root.right, mid + 1, end);
}
}
// Driver code
public static void main (String[] args)
{ int[] nums = {1, 3, 5}; int start = 0, end = 2;
segmentTreeNode root = new segmentTreeNode(start, end);
//System.out.println("sumRange(start, end) is " +
// sumRange(start, end));
System.out.println("executed");
}
} // Contributed by Prakriti Gupta