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

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;