Fenwick Tree Java <p>I tried to implement the Fenwick Tree in Java, but I am not getting the desired result. Here is my code:</p> <pre><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 &lt; 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 &lt; a.length) { a[at] += by; at |= (at + 1); } } public static int query(int at) { int res = 0; while (at &gt;= 0) { res += a[at]; at = (at &amp; (at + 1)) - 1; } return res; } } </code></pre> <p>When I give input: </p> <blockquote> <p>10<br> 1 2 3 4 5 6 7 8 9 10 </p> </blockquote> <p>I get: </p> <blockquote> <p>13<br> 19</p> </blockquote> <p>So the increment function works fine. But query(4) should give the cumulative sum up to index 4 i.e.</p> <blockquote> <p>(1 + 2 + 13 + 4 + 5) = 25</p> </blockquote>