[Link] https://www.acmicpc.net/problem/11659
I solved this with segment tree since I wanted to pratice it. It’s actually faster just using sum[i]: sum of arr[0] ~ arr[i]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
import java.util.*;
import java.io.*;
public class Main {
public static void main(String args[]) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
String[] line = br.readLine().split(" ");
int n = atoi(line[0]), m = atoi(line[1]);
int[] nums = new int[n];
line = br.readLine().split(" ");
int size = (int)Math.ceil((Math.log(n)/Math.log(2)));
size = 1 << (size + 1);
int[] seg = new int[size];
for(int i = 0; i < n; i++) {
nums[i] = atoi(line[i]);
}
init(seg, nums, 0, n - 1, 1);
for(int i = 0; i < m; i++) {
line = br.readLine().split(" ");
int start = atoi(line[0]) - 1, end = atoi(line[1]) - 1;
System.out.println(sum(seg, start, end, 0, n - 1, 1));
}
}
public static int init(int[] seg, int[] arr, int l, int r, int idx) {
if(l == r) return seg[idx] = arr[l];
int mid = (l + r) / 2;
return seg[idx] = init(seg, arr, l, mid, 2 * idx) + init(seg, arr, mid + 1, r, 2 * idx + 1);
}
public static int sum(int[] seg, int start, int end, int l, int r, int idx) {
if(r < start || l > end) return 0;
if(start <= l && r <= end) {
return seg[idx];
}
int mid = (l + r) / 2;
return sum(seg, start, end, l, mid, idx * 2) + sum(seg, start, end, mid + 1, r, idx * 2 + 1);
}
public static int atoi(String s) { return Integer.parseInt(s); }
}