# Interval Sum I && II

Interval Sum I

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) {
} else {
}

}
return result;
}```

Interval Sum II

Given an integer array in the construct method, implement two methods `query(start, end)` and`modify(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)`, return `10`.
• `modify(0, 4)`, change A[0] from 1 to 4.
• `query(0, 1)`, return `6`.
• `modify(2, 1)`, change A[2] from 7 to 1.
• `query(2, 4)`, return `14`.

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.

```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;
}
}
}```
Share