芬威克树的Java [英] Fenwick Tree Java

问题描述

我试图实现树状数组在Java中，但我没有得到期望的结果。 这是我的code：

 进口java.io. *;
导入的java.util。*;
导入的java.math *。

类fenwick1 {
    公共静态INT N;
    公共静态长[]一个;
    公共静态无效的主要（字串[] args）抛出IOException异常{
        的BufferedReader BR =新的BufferedReader（新的InputStreamReader（System.in））;
        N =的Integer.parseInt（br.readLine（））;
        A =新长[N];
        的String []海峡= br.readLine（）分裂（）。
        的for（int i = 0; I＆n种;我++）{
            A [1] =的Long.parseLong（STR [I]）;
        }
        增量（2，10）;
        的System.out.println（一个[2]）;
        的System.out.println（查询（4））;
    }

    公共静态无效的增量（INT时，通过INT）{
        而（AT＆LT;则为a.length）{
            一[在] + =通过;
            在| =（在+ 1）;
        }
    }

    公共静态INT查询（INT的）{
        INT RES = 0;
        而（AT＆GT; = 0）{
            RES + = A [在];
            在=（在及（在+ 1）） -  1;
        }
        返回水库;
    }
}
 

当我给输入：

  

10
  1 2 3 4 5 6 7 8 9 10

我得到：

  

13
  19

因此​​，增加功能工作正常。但查询（4）应给予累计金额达指数4，即

  

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

解决方案

您不初始化正确。 相反的：

 的for（int i = 0; I＆n种;我++）{
    A [1] =的Long.parseLong（STR [I]）;
}
 

这应该是：

 的for（int i = 0; I＆n种;我++）{
    增量（我，（INT）的Long.parseLong（STR（I）））;
}
 

由于 A [1] 应存储的累加值，而不是一个单一的元素。

如果你想存储初始数组元素太多，你可以再创建一个数组：

 长[] INITA =新长[N];
的for（int i = 0; I＆n种;我++）{
    INITA [I] =的Long.parseLong（STR [I]）;
    增量（ⅰ，（int）的INITA [I]）;
}
 

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

解决方案

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]);
}

这篇关于芬威克树的Java的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！