如何在 Java 中利用数组实现简单的前缀和（Prefix Sum）技术以支持 O(1) 时间的区间查询-java教程-PHP中文网

前缀和通过预处理数组实现O(1)区间求和：构建长度n+1的prefix数组，prefix[0]=0，prefix[i]=prefix[i-1]+nums[i-1]，则[left,right]和为prefix[right+1]-prefix[left]。

如何在 java 中利用数组实现简单的前缀和（prefix sum）技术以支持 o(1) 时间的区间查询

在 Java 中，前缀和是一种通过预处理数组来加速区间求和查询的常用技巧。核心思想是：预先计算一个新数组 prefix，其中 prefix[i] 表示原数组从索引 0 到 i（含）的所有元素之和。这样，任意区间 [left, right] 的和就能用一次减法在 O(1) 时间内得到。

构造前缀和数组

假设原始数组为 nums，长度为 n，我们构建长度为 n 的前缀和数组（0-indexed），或更常用的是长度为 n + 1 的“带哨兵”版本（避免边界特判）。推荐使用后者：

定义 prefix[0] = 0
对每个 i 从 1 到 n，令 prefix[i] = prefix[i - 1] + nums[i - 1]
此时 prefix[i] 表示 nums[0..i-1] 的和

实现 O(1) 区间查询

给定查询区间 [left, right]（闭区间，0 ≤ left ≤ right

sum = prefix[right + 1] - prefix[left]

这是因为：

Java注释规范Skills

当用户要求为 Java 代码添加注释、修改注释、审查注释、整理注释格式，或要求按照代码注释规范处理 Java 文件时，使用本技能。本技能用于统一生成和维护 Java 类注释模板、按 Git 对比 release 判断版本号、补充每行代码上方中文块注释、调整注释空行规则，并保持 Java 文件 UTF-8 无 BOM 编码。典型触发场景包括：补充类注释、更新 @version、检查 @author 来源、整理行尾注释、把注释放到代码上一行、检查注释是否符合规范、构建前检查 Java 注释风格。

下载

prefix[right + 1] = nums[0] + ... + nums[right]
prefix[left] = nums[0] + ... + nums[left - 1]
相减后剩下 nums[left] + ... + nums[right]

Java 示例代码

以下是一个完整、可运行的示例：

<font size="2"><pre class="brush:php;toolbar:false;">public class PrefixSum {
    private int[] prefix;
<pre class="brush:java;toolbar:false;">public PrefixSum(int[] nums) {
    int n = nums.length;
    prefix = new int[n + 1];
    for (int i = 1; i <p>}</p>