最基本的来自https://leetcode.com/problems/range-sum-query-mutable/
class NumArray { int[ ] nums = null; int[ ] tree = null; int n = 0; public NumArray(int[] nums) { this.nums = nums; n = nums.length; tree = new int[2*n]; for(int i=n; i<=2*n-1; ++i) tree[i] = nums[i-n]; for(int i=n-1; i>0; --i) tree[i] = tree[2*i]+tree[2*i+1]; } public void update(int i, int val) { int diff = val - nums[i]; nums[i] = val; for(int p=i+n;p>0;p/=2){ tree[p] += diff; } } public int sumRange(int i, int j) { int left = i+n, right = j+n; int sum = 0; while(left<=right){ if(left==right){ sum += tree[left]; return sum; } if(left%2==1){ sum += tree[left++]; } if(right%2==0){ sum += tree[right--]; } left /= 2; right >>>= 1; } return sum; } }调用：
int[] nums = {1,3,5}; NumArray obj = new NumArray(nums); obj.sumRange(0, 2);// -> 9 obj.update(1, 2); obj.sumRange(0, 2);// -> 8待深入的话题：离散化，插入，lazy更新
待用线段树解决的问题： 1，https://leetcode.com/problems/the-skyline-problem/ 2，https://codingcompetitions.withgoogle.com/kickstart/round/0000000000050eda/00000000001198c1
