1

I tried to implement the Fenwick Tree in Java, but I am not getting the desired result. Here is my code:

import java.io.*;
import java.util.*;
import java.math.*;

class fenwick1 {
    public static int N;
    public static long[] a;
    public static void main(String[] args)throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        N = Integer.parseInt(br.readLine());
        a = new long[N];
        String[] str = br.readLine().split(" ");
        for (int i = 0; i < N; i++) {
            a[i] = Long.parseLong(str[i]);
        }
        increment(2, 10);
        System.out.println(a[2]);
        System.out.println(query(4));
    }

    public static void increment(int at, int by) {
        while (at < a.length) {
            a[at] += by;
            at |= (at + 1);
        }
    }

    public static int query(int at) {
        int res = 0;
        while (at >= 0) {
            res += a[at];
            at = (at & (at + 1)) - 1;
        }
        return res;
    }
}

When I give input:

10
1 2 3 4 5 6 7 8 9 10

I get:

13
19

So the increment function works fine. But query(4) should give the cumulative sum up to index 4 i.e.

(1 + 2 + 13 + 4 + 5) = 25

AndyG
  • 39,700
  • 8
  • 109
  • 143
user2784016
  • 179
  • 1
  • 7

1 Answers1

1

You do not initialize it properly. Instead of:

for (int i = 0; i < N; i++) {
    a[i] = Long.parseLong(str[i]);
}

It should be:

for (int i = 0; i < N; i++) {
    increment(i, (int)Long.parseLong(str[i]));
}

because a[i] should store a cumulative sum, not a single element.

If you want to store the initial array elements too, you can just create one more array:

long[] initA = new long[N];
for (int i = 0; i < N; i++) {
    initA[i] = Long.parseLong(str[i]);
    increment(i, (int)initA[i]);
}
kraskevich
  • 18,368
  • 4
  • 33
  • 45
  • If the original array is {1, 1, 1, 1, 1, 1, 1, 1, 1, 1}, then a = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}. After increment(2, 10), a = {1, 2, 13, 4, 5, 6, 7, 8, 9, 10}. Is it correct? – user2784016 Oct 10 '14 at 13:33
  • @user2784016 No, it is not correct. `a[i]` stores a cumulative sum from `i & (i + 1)` to `i`, not the entire prefix sum. initially `a = {1, 2, 1, 4, 1, 2, 1, 8, 1, 2}`. After adding `10` it is `{1, 2, 11, 14, 1, 2, 1, 18, 1, 2}`. – kraskevich Oct 10 '14 at 13:39
  • I want to initialize an array (not cumulative sum) in array a.Then I need to increment some element and find cumulative sum up to some index using Fenwick tree. Can you please modify my code to solve this problem? – user2784016 Oct 10 '14 at 13:44
  • @user2784016 Then you need to arrays: the first one for the array itself and the other one for cumulative sums. – kraskevich Oct 10 '14 at 13:51
  • Then I use the increment and query functions on the cumulative array and get the answers for the original array. Isn't it? – user2784016 Oct 10 '14 at 14:18