一维前缀和

一维前缀和适用于快速计算数组的区间和。其核心思想是通过预处理构建一个前缀和数组，使得后续查询可以在常数时间内完成。

区间和查询

定义前缀和数组sum，其中sum[i]表示原数组前i个元素的和。预处理公式为： sum[i] = sum[i-1] + a[i] 

计算区间[l, r]的和时，只需使用： sum[r] - sum[l-1]

创建前缀和数组时，通常从索引1开始存储数据，方便处理边界条件。初始化时数组长度设为n+1，预留sum[0]=0作为边界值。

原理

例题

B3612 【深进1.例1】求区间和 - 洛谷

示例代码

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int n=sc.nextInt();
        int sum[]=new int[n+1];
        for(int i=1;i<=n;i++){
            int a=sc.nextInt();
            sum[i]=sum[i-1]+a;
        }
        int m=sc.nextInt();
        for(int i=1;i<=m;i++){
            int l=sc.nextInt();
            int r=sc.nextInt();
            System.out.println(sum[r]-sum[l-1]);
        }
    }
}

二维前缀和

二维前缀和扩展了一维的思想，用于快速计算矩阵的子矩阵和。预处理时需要递推计算每个位置的前缀和。

区间和查询

定义二维前缀和数组sum，其中sum[i][j]表示从(1,1)到(i,j)的子矩阵和。预处理公式为： sum[i][j] = sum[i-1][j] + sum[i][j-1] - sum[i-1][j-1] + a[i][j] 

计算子矩阵(u,v)到(x,y)的和时，使用：  sum[x][y] - sum[u-1][y] - sum[x][v-1] + sum[u-1][v-1]

创建前缀和数组时，通常从索引1开始存储数据，方便处理边界条件。

原理

例题

B3693 数列前缀和 4 - 洛谷

示例代码

import java.util.Scanner;
public class Main{
    public static void main(String[]args){
        Scanner sc=new Scanner(System.in);
        int t=sc.nextInt();
        for(int i=1;i<=t;i++){
            int n=sc.nextInt();
            int m=sc.nextInt();
            int q=sc.nextInt();
            long sum[][]=new long[n+1][m+1];
            for(int j=1;j<=n;j++){
                for(int k=1;k<=m;k++){
                    int a=sc.nextInt();
                    sum[j][k]=sum[j-1][k]+sum[j][k-1]-sum[j-1][k-1]+a;
                }
            }
            long result=0;
            for(int r=1;r<=q;r++){
                int u=sc.nextInt();
                int v=sc.nextInt();
                int x=sc.nextInt();
                int y=sc.nextInt();
                long s=sum[x][y]-sum[u-1][y]-sum[x][v-1]+sum[u-1][v-1];
                result^=s;
            }
            System.out.println(result);
        }
    }
}

注意事项

• 数组下标通常从1开始，避免边界判断
• 注意数据范围，必要时使用long类型防止溢出
• 预处理时间复杂度为O(n)或O(n²)，查询时间为O(1)