我尝试用 Java 实现分域树,但没有得到想要的结果。 这是我的代码:
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;
}
}
当我输入时:
10
1 2 3 4 5 6 7 8 9 10
我得到:
13
19
所以增量函数工作正常。但是 query(4) 应该给出索引 4 的累积总和,即
(1 + 2 + 13 + 4 + 5) = 25
最佳答案
您没有正确初始化它。 而不是:
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]);
}
关于java - 芬威克树 java ,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/26299990/