Summing integers in stream using Fenwick tree

Question

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 tree
• create() create the fenwick tree
• update() update the fenwick tree
• sum() return the sum by fenwick tree

update :

• add Arrays.fill(FT, 0); to initialize Fenwick tree
• create() use update()
• 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;
 }
}

• jacwah: Welcome to Code Review! Could you edit the question to include a more complete description of the challenge? At first, I thought "sum from a to b" meant to sum the integers from a to b, which doesn't seem to be the problem at all.
• jacwah: On Code Review we generally try to write a title that summarizes what our code does, not what we want to get out of a review. I edited your title to one I felt described your program better. You may also want to read How to get the best value out of Code Review - Asking Questions.
• Kiwi Lin: Learning programming and English, thank you a lot.

Answer 1

Incorrect creation of fenwick tree

Your function create() is both incorrect and slow. You had the correct function update() but you never used it. Instead you tried to create the fenwick tree yourself but used an \$O(n^2)\$ algorithm to do so. The correct way would have been just:

public static void create() {
 for (int i = 1; i <= N; i++) {
 update(i, array[i]);
 }
}

This would have created the fenwick tree in \$O(n \log n)\$ time.

Bug

Another problem you have is when you update the array. You do correctly update the fenwick tree, but you forgot to update the actual array. In other words, after this line:

 update(x, y - array[x]);

you need this line:

 array[x] = y;

• Kiwi Lin: Your comment is helpful to me, but it still not passed on UVa. ( I add Arrays.fill(FT, 0); to initialize the Fenwick tree . Is it not good ?)
• JS1: @HsMion Check my latest edit.
• Kiwi Lin: I edited the code.
• JS1: @HsMion Actually, on this site, you aren't supposed to edit your code.
• Kiwi Lin: I got it, I 'll take care of that. Thanks for your reminder. Back to the question, does it build a fenwick tree class would be fast ? I found other people use class to solve the problem. My code still exceed the time limit.