2026-01-21-牛客每日一题-静态区间和（前缀和）

title: 2026-01-21-牛客每日一题-静态区间和（前缀和）
date: 2026-01-21
tags:

• 算法学习
• 牛客
• 前缀和

题目信息

• 平台：牛客
• 题目：【模板】静态区间和（前缀和）
• 难度：简单（模板）
• 题目链接

题目描述

给定长度为 n 的数组和 q 次查询，每次给出区间 [l, r]，输出该区间元素之和。数组不修改。

初步思路

1. 朴素做法

如果每次查询都直接遍历区间[l, r]求和，时间复杂度为O(n)。对于q次查询，总时间复杂度为O(nq)。

2. 前缀和优化

我们需要快速求出区间和，利用前缀和可以将区间查询优化到O(1)。

定义：
令pre[i]表示数组前i个元素的和，即：
p r e [ i ] = a [ 1 ] + a [ 2 ] + ⋯ + a [ i ] pre[i] = a[1] + a[2] + \dots + a[i]pre[i]=a[1]+a[2]+⋯+a[i]
特别地，定义pre[0] = 0。

推导区间和：
我们需要求区间[l, r]的和：
s u m ( l , r ) = a [ l ] + a [ l + 1 ] + ⋯ + a [ r ] sum(l, r) = a[l] + a[l+1] + \dots + a[r]sum(l,r)=a[l]+a[l+1]+⋯+a[r]

我们可以用pre[r]减去pre[l-1]来得到：

• pre[r]包含了a[1]...a[r]
• pre[l-1]包含了a[1]...a[l-1]
• 相减后，1到l-1部分着消，剩下l到r部分。

公式：
s u m ( l , r ) = p r e [ r ] − p r e [ l − 1 ] sum(l, r) = pre[r] - pre[l-1]sum(l,r)=pre[r]−pre[l−1]

3. 一个例子

以数组a = [1, 2, 3, 4, 5]为例：

• pre[3] = 1 + 2 + 3 = 6
• pre[1] = 1

我们要求区间[2, 3]的和，即a[2] + a[3] = 2 + 3 = 5。

根据公式sum(2, 3) = pre[3] - pre[1]：
pre [ 3 ] = 1 + 2 + 3 pre [ 1 ] = 1 pre [ 3 ] − pre [ 1 ] = ( 1 + 2 + 3 ) − ( 1 ) = 2 + 3 = 5 \begin{aligned} \text{pre}[3] &= 1 + 2 + 3 \\ \text{pre}[1] &= 1 \\ \text{pre}[3] - \text{pre}[1] &= (1 + 2 + 3) - (1) \\ &= 2 + 3 \\ &= 5 \end{aligned}pre[3]pre[1]pre[3]−pre[1]​=1+2+3=1=(1+2+3)−(1)=2+3=5​

4. 复杂度

• 预处理：O(n)
• 每次查询：O(1)
• 总时间复杂度：O(n + q)

算法分析

• 核心：前缀和转化区间求和
• 技巧：pre[0] = 0，使用 long long 防止溢出
• 时间复杂度：O(n + q)
• 空间复杂度：O(n)

代码实现（C++）

#include<iostream>#include<vector>usingnamespacestd;intmain(){ios::sync_with_stdio(false);cin.tie(nullptr);intn,q;cin>>n>>q;vector<longlong>pre(n+1,0);for(inti=1;i<=n;++i){longlongx;cin>>x;pre[i]=pre[i-1]+x;}while(q--){intl,r;cin>>l>>r;cout<<pre[r]-pre[l-1]<<'\n';}return0;}

总结与反思

1. 静态区间和用前缀和是最直接且高效的模板解法。
2. 注意区间下标从 1 开始时，pre 的边界处理。