Fenwick Tree Java

我尝试用Java实现Fenwick树，但是我没有得到理想的结果。 这是我的代码：

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 = 0) { res += a[at]; at = (at & (at + 1)) - 1; } return res; } } 

当我给出输入时：

10
1 2 3 4 5 6 7 8 9 10

我明白了：

13
19

因此增量函数工作正常。 但查询（4）应该给出索引4的累积总和即

（1 + 2 + 13 + 4 + 5）= 25

Answer 1

您没有正确初始化它。 代替：

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

它应该是：

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

因为a[i]应该存储累积总和，而不是单个元素。

如果您还想存储初始数组元素，则可以再创建一个数组：

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