1

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

4

1 に答える 1

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]単一の要素ではなく、累積合計を格納する必要があるためです。

初期配列要素も格納したい場合は、もう 1 つの配列を作成するだけです。

long[] initA = new long[N];
for (int i = 0; i < N; i++) {
    initA[i] = Long.parseLong(str[i]);
    increment(i, (int)initA[i]);
}
于 2014-10-10T13:24:27.053 に答える