LintCode:区间求和 II
class SegmentTreeNode { public int start, end; long max; public SegmentTreeNode left, right; public SegmentTreeNode(int start, int end, long max) { this.start = start; this.end = end; this.max = max; this.left = this.right = null; } } public class Solution { /* you may need to use some attributes here */ /** * @param A: An integer array */ long res; int[] A; SegmentTreeNode root; public Solution(int[] A) { // write your code here if (A.length ==0){ return; } this.A = A; int n = A.length - 1; long root_val = sum(A, 0, n); root = new SegmentTreeNode(0, n, root_val); buildSegmentTree(root, A); } /** * @param start, end: Indices * @return: The sum from start to end */ public long query(int start, int end) { // write your code here res = 0; myQuery(root, start, end); return res; } /** * @param index, value: modify A[index] to value. */ public void modify(int index, int value) { // write your code here int tmp = value - this.A[index]; this.A[index] = value; myModify(root, index, tmp); } private void buildSegmentTree(SegmentTreeNode root, int[] A){ if(root.start == root.end){ return; } int left_start = root.start; int left_end = (root.start + root.end) / 2; long left_val = sum(A, left_start, left_end); root.left = new SegmentTreeNode(left_start, left_end, left_val); int right_start = (root.start + root.end) / 2 + 1; int right_end = root.end; long right_val = sum(A, right_start, right_end); root.right = new SegmentTreeNode(right_start, right_end, right_val); buildSegmentTree(root.left, A); buildSegmentTree(root.right, A); } public long sum(int[] A, int start, int end){ res = 0; for(int i=start; i<=end; i++){ res += A[i]; } return res; } public void myQuery(SegmentTreeNode root, int start, int end){ if (start > root.end || end < root.start){ return; } if (start <= root.start && end >= root.end){ res += root.max; return; } myQuery(root.left, start, end); myQuery(root.right, start, end); } public void myModify(SegmentTreeNode root, int index, int tmp){ if(root != null && root.start <= index && root.end >= index){ root.max += tmp; } else{ return; } myModify(root.left, index, tmp); myModify(root.right, index, tmp); } }