In short, the input is an ordered list of numbers, and we have to sum the numbers from index a to b quickly. For example, assume array[] = {1, 2, 3}
. Please sum from array[0]
to array[2]
(1 + 2 + 3
).
Because the input array can have as much as 200,000 elements, I used a Fenwick tree to save time, but the time limit is still exceeded on UVa.
Here is the problem on UVa.
Which part can I improve?
I built:
lowbit()
return low bit for fenwick treecreate()
create the fenwick treeupdate()
update the fenwick treesum()
return the sum by fenwick tree
update :
- add
Arrays.fill(FT, 0);
to initialize Fenwick tree create()
useupdate()
- add
array[x] = y;
to update the actual array
import java.util.*;
public class Main {
static int[] FT = new int[200001]; /* store fenwick tree */
static int[] array = new int[200001]; /* store input data */
static int N; /* size of input data */
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int testCase = 0; /* not important, just for UVa output format*/
int x, y;
while ((N = in.nextInt()) > 0) {
Arrays.fill(FT, 0); /* Initialize Fenwick tree */
for (int i = 1; i <= N; i++) { /* Initialize input array */
array[i] = in.nextInt();
}
create();
System.out.printf("Case %d:\n", ++testCase);
String act;
while (!(act = in.next()).equals("END")) { /* receive action: print sum, update data or END */
if (act.equals("M")) { /* to print sum from x to y*/
x = in.nextInt();
y = in.nextInt();
System.out.println(sum(y) - sum(x - 1));
} else { /* to update the array[x] to y ,also fenwick tree*/
x = in.nextInt();
y = in.nextInt();
update(x, y - array[x]);
array[x] = y;
}
}
}
}
public static void create() {
for (int i = 1; i <= N; i++) {
update(i, array[i]);
}
}
public static void update(int i, int delta) {
for (int j = i; j <= N; j += lowbit(j)) {
FT[j] += delta;
}
}
public static int sum(int k) {
int ans = 0;
for (int i = k; i > 0; i -= lowbit(i)) {
ans += FT[i];
}
return ans;
}
public static int lowbit(int k) {
return -k & k;
}
}