数组前缀和计算 Java

数组前缀和是指将数组中从第一个元素开始到当前元素的所有元素的和保存到另一个数组中。这个操作可以优化某些算法的时间复杂度。以下是 Java 代码实现：

public static int[] prefixSum(int[] arr) {
    if (arr == null || arr.length == 0) {
        return null;
    }
    int[] prefix = new int[arr.length];
    prefix[0] = arr[0];
    for (int i = 1; i < arr.length; i++) {
        prefix[i] = prefix[i-1] + arr[i];
    }
    return prefix;
}

这个方法接收一个整型数组 `arr` 作为输入，并返回一个新的整型数组 `prefix`，其中 `prefix[i]` 表示数组 `arr` 中从第一个元素到第 `i` 个元素的和。在方法中，我们首先检查输入数组是否为空，如果为空则返回 `null`。如果不为空，则创建一个与输入数组长度相同的新数组 `prefix`，并将 `prefix[0]` 初始化为 `arr[0]`。然后我们使用一个循环遍历数组 `arr` 中的每个元素，计算出当前元素之前所有元素的和，并将结果保存到 `prefix` 数组中。最后返回 `prefix` 数组即可。

相关问题

java写一段求一个一维数组的前缀和

计算一维数组的前缀和的java代码如下：int[] arr = {1,2,3,4,5};int[] prefixSum = new int[arr.length];prefixSum[0] = arr[0];for (int i = 1; i < arr.length; i++) {
prefixSum[i] = prefixSum[i - 1] + arr[i];
}

java实现树状数组区间修改查询

树状数组（Fenwick Tree）是一种用于高效计算数组前缀和的数据结构。它可以支持单点修改和区间查询，但是不能直接支持区间修改，需要进行一些变形。

一般情况下，树状数组被用于求解静态数组的前缀和，这里我们介绍一种树状数组的变形——动态树状数组。该数据结构可以支持区间修改和区间查询，时间复杂度均为 O(log n)。

动态树状数组的实现分为两步：

1. 实现区间修改。为了实现区间修改，我们需要维护两个树状数组：A 和 B。A 保存原数组，B 保存它们的差值。当我们要修改区间 [l, r]，我们可以直接对 A[l] 和 A[r+1] 进行修改，让它们的值分别加上 val 和 -val。同时，我们也需要对 B[l] 和 B[r+1] 进行相同的修改，让它们的值分别加上 val * l 和 -val * (r+1)。这样，当我们查询区间和时，只需要查询 A 和 B 中的差值和即可。

2. 实现区间查询。为了实现区间查询，我们需要对查询区间 [l, r] 进行拆分。我们可以将查询区间拆分为两个前缀和：[1, r] 和 [1, l-1]。然后，我们可以对这两个前缀和分别进行查询，相减即可得到区间和。

下面是 Java 代码实现：

public class DynamicFenwickTree {
    private int[] a;
    private int[] b;

    public DynamicFenwickTree(int n) {
        a = new int[n + 1];
        b = new int[n + 1];
    }

    public void update(int l, int r, int val) {
        update(a, l, val);
        update(a, r + 1, -val);
        update(b, l, val * l);
        update(b, r + 1, -val * (r + 1));
    }

    public int query(int l, int r) {
        return query(r) - query(l - 1);
    }

    private void update(int[] t, int i, int val) {
        while (i < t.length) {
            t[i] += val;
            i += i & -i;
        }
    }

    private int query(int[] t, int i) {
        int sum = 0;
        while (i > 0) {
            sum += t[i];
            i -= i & -i;
        }
        return sum;
    }

    private int query(int i) {
        return query(a, i) * i - query(b, i);
    }
}

使用示例：

DynamicFenwickTree tree = new DynamicFenwickTree(5);
tree.update(1, 3, 2);
tree.update(2, 4, 3);
System.out.println(tree.query(1, 5)); // 20

这个例子中，我们创建了一个长度为 5 的动态树状数组，然后使用 update 方法对区间 [1, 3] 和 [2, 4] 进行了修改，分别加上了 2 和 3。最后，我们使用 query 方法查询了整个数组的和，结果为 20。