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
这道题最简便的方法当然是prefix Sum
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
public class Solution {
/**
*@param A, queries: Given an integer array and an query list
*@return: The result list
*/
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
/**
* Definition of Interval:
* public classs Interval {
* int start, end;
* Interval(int start, int end) {
* this.start = start;
* this.end = end;
* }
*/
public class Solution {
/**
*@param A, queries: Given an integer array and an query list
*@return: The result list
*/
public class SegmentTreeNode {
long sum;
int start;
int end;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.sum = 0;
this.start = start;
this.end = end;
this.left = null;
this.right = null;
}
} SegmentTreeNode root; public ArrayList<Long> intervalSum(int[] A,
ArrayList<Interval> queries) {
// write your code here
ArrayList<Long> res = new ArrayList<Long>();
root = build(A, 0, A.length-1);
for (Interval interval : queries) {
int start = interval.start;
int end = interval.end;
res.add(query(root, start, end));
}
return res;
} public SegmentTreeNode build(int[] A, int start, int end) {
SegmentTreeNode cur = new SegmentTreeNode(start, end);
if (start == end) {
cur.sum = A[start];
}
else {
int mid = (start + end)/2;
cur.left = build(A, start, mid);
cur.right = build(A, mid+1, end);
cur.sum = cur.left.sum + cur.right.sum;
}
return cur;
} public Long query(SegmentTreeNode cur, int start, int end) {
if (cur.start==start && cur.end==end) return cur.sum;
int mid = (cur.start + cur.end)/2;
if (end <= mid) return query(cur.left, start, end);
else if (start > mid) return query(cur.right, start, end);
else return query(cur.left, start, mid) + query(cur.right, mid+1, end);
}
}