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.
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
Solution: Version 1. prefix sum,
(Version 2. Segment tree: check Interval Sum II)
public ArrayList<Long> intervalSum(int[] A,
ArrayList<Interval> queries) {
//Version 1. prefix sum,
//Version 2. Segment tree: check Interval Sum II
ArrayList<Long> result = new ArrayList<>();
if (A == null || queries == null || A.length == 0 || queries.size() == 0) {
return result;
}
Long[] prefixSum = new Long[A.length];
Long sum = 0L;
for (int i = 0; i < A.length; i++) {
sum += A[i];
prefixSum[i] = sum;
}
for (Interval interval : queries) {
if (interval.start == 0) {
result.add(prefixSum[interval.end]);
} else {
result.add(prefixSum[interval.end] - prefixSum[interval.start - 1]);
}
}
return result;
}
Given an integer array in the construct method, implement two methods query(start, end) andmodify(index, value):
- For query(start, end), return the sum from index start to index end in the given array.
- For modify(index, value), modify the number in the given index to value
Example
Given array A = [1,2,7,8,5].
query(0, 2), return10.modify(0, 4), change A[0] from 1 to 4.query(0, 1), return6.modify(2, 1), change A[2] from 7 to 1.query(2, 4), return14.
Note
We suggest you finish problem Segment Tree Build, Segment Tree Query and Segment Tree Modify first.
Challenge
O(logN) time for query and modify.
Solution: Segment Tree.
建立：O(n) 时间
查询：O(logN) 时间
更改其中一个元素: O(logN)
public class Solution {
SegmentTreeNode root;
public class SegmentTreeNode {
int start, end;
int sum;
SegmentTreeNode left;
SegmentTreeNode right;
public SegmentTreeNode(int start, int end) {
this.start = start;
this.end = end;
}
}
public Solution(int[] A) {
if (A == null || A.length == 0) {
return;
}
this.root = buildSegmentTree(A, 0, A.length - 1);
}
private SegmentTreeNode buildSegmentTree(int[] A, int start, int end) {
SegmentTreeNode node = new SegmentTreeNode(start, end);
if (start == end) {
node.sum = A[start];
} else {
int mid = start + (end - start) / 2;
node.left = buildSegmentTree(A, start, mid);
node.right = buildSegmentTree(A, mid + 1, end);
node.sum = node.left.sum + node.right.sum;
}
return node;
}
public long query(int start, int end) {
if (start < this.root.start || end > this.root.end) {
return -1;
}
return query(this.root, start, end);
}
private long query(SegmentTreeNode root, int start, int end) {
if (root.start == start && root.end == end) {
return root.sum;
}
int mid = root.start + (root.end - root.start) / 2;
long leftSum = 0L, rightSum = 0L;
if (start <= mid) {
if (end <= mid) {
leftSum = query(root.left, start, end);
} else {
leftSum = query(root.left, start, mid);
}
}
if (end > mid) {
if (start > mid) {
rightSum = query(root.right, start, end);
} else {
rightSum = query(root.right, mid + 1, end);
}
}
return leftSum + rightSum;
}
public void modify(int index, int value) {
modify(this.root, index, value);
}
public void modify(SegmentTreeNode root, int index, int value) {
if (root.start == index && root.end == index) {
root.sum = value;
} else {
int mid = root.start + (root.end - root.start) / 2;
if (index <= mid) {
modify(root.left, index, value);
} else {
modify(root.right, index, value);
}
root.sum = root.left.sum + root.right.sum;
}
}
}
