http://www.cnblogs.com/EdwardLiu/p/5176673.html
这道题最简便的方法当然是prefix Sum
Given an integer array (index from 0 to n-1, where n is the size of this array), and an query list. Each query has two integers [start, end]. For each query, calculate the sum number between index start and end in the given array, return the result list. Have you met this question in a real interview? Yes Example For array [1,2,7,8,5], and queries [(0,4),(1,2),(2,4)], return [23,9,20] Note We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first. Challenge O(logN) time for each query
public ArrayList<Long> intervalSum(int[] A, ArrayList<Interval> queries) { // write your code here long[] prefixSum = new long[A.length+1]; for (int i=0; i<A.length; i++) { prefixSum[i+1] = prefixSum[i] + A[i]; } ArrayList<Long> res = new ArrayList<Long>(); for (Interval interval : queries) { int start = interval.start; int end = interval.end; long result = prefixSum[end+1] - prefixSum[start]; res.add(result); } return res; }
用Segment Tree
15 public class SegmentTreeNode { 16 long sum; 17 int start; 18 int end; 19 SegmentTreeNode left; 20 SegmentTreeNode right; 21 public SegmentTreeNode(int start, int end) { 22 this.sum = 0; 23 this.start = start; 24 this.end = end; 25 this.left = null; 26 this.right = null; 27 } 28 } 29 30 SegmentTreeNode root; 31 32 public ArrayList<Long> intervalSum(int[] A, 33 ArrayList<Interval> queries) { 34 // write your code here 35 ArrayList<Long> res = new ArrayList<Long>(); 36 root = build(A, 0, A.length-1); 37 for (Interval interval : queries) { 38 int start = interval.start; 39 int end = interval.end; 40 res.add(query(root, start, end)); 41 } 42 return res; 43 } 44 45 public SegmentTreeNode build(int[] A, int start, int end) { 46 SegmentTreeNode cur = new SegmentTreeNode(start, end); 47 if (start == end) { 48 cur.sum = A[start]; 49 } 50 else { 51 int mid = (start + end)/2; 52 cur.left = build(A, start, mid); 53 cur.right = build(A, mid+1, end); 54 cur.sum = cur.left.sum + cur.right.sum; 55 } 56 return cur; 57 } 58 59 public Long query(SegmentTreeNode cur, int start, int end) { 60 if (cur.start==start && cur.end==end) return cur.sum; 61 int mid = (cur.start + cur.end)/2; 62 if (end <= mid) return query(cur.left, start, end); 63 else if (start > mid) return query(cur.right, start, end); 64 else return query(cur.left, start, mid) + query(cur.right, mid+1, end); 65 }