力扣数组
区间和
区间和
https://kamacoder.com/problempage.php?pid=1070
题目
给定一个整数数组 numsay，请计算该数组在每个指定区间内元素的总和。
输入描述 第一行输入为整数数组 numsay 的长度 n，接下来 n 行，每行一个整数，表示数组的元素。随后的输入为需要计算总和的区间下标：a，b（b >= a），直至文件结束。
输出描述 输出每个指定区间内元素的总和。
输入示例
5
1
2
3
4
5
0 1
1 3输出示例
3
9提示信息 数据范围：0 < n <= 100000
思路
核心逻辑：直接遍历区间求和会导致多次查询时时间复杂度偏高（最坏O(n*q)，q为查询次数），因此采用前缀和数组优化：
- 构建前缀和数组
prefix，其中prefix[0] = 0，prefix[i]表示原数组前i个元素的和（即numsay[0] + numsay[1] + ... + numsay[i-1]）； - 区间
[a, b]的和 =prefix[b+1] - prefix[a]； - 预处理前缀和数组的时间复杂度为 O(n)，每次查询的时间复杂度为 O(1)，整体时间复杂度优化为 O(n + q)，能高效处理大数据量和多次查询场景。
解法
import sys
def main():
data = sys.stdin.read().split()
index = 0
n = int(data[index])
index += 1
nums = []
for _ in range(n):
nums.append(int(data[index]))
index += 1
prefix = [0] * (n + 1)
for i in range(1, n + 1):
prefix[i] = prefix[i-1] + nums[i-1]
while index < len(data):
a = int(data[index])
b = int(data[index+1])
index += 2
res = prefix[b+1] - prefix[a]
print(res)
if __name__ == "__main__":
main()解释
| 代码片段 | 作用与原因 |
|---|---|
import sys + data = sys.stdin.read().split() | 读取全部输入并分割为列表，避免逐行读取的IO开销，适配大数据量场景（n<=1e5） |
index 指针 | 遍历分割后的输入列表，精准定位当前读取位置，避免多次切片操作 |
prefix = [0] * (n + 1) | 前缀和数组长度为n+1，prefix[0] = 0 作为基准，简化区间和计算逻辑 |
prefix[i] = prefix[i-1] + nums[i-1] | 构建前缀和：prefix[i] 累加原数组第i-1个元素，保证前缀和的定义一致性 |
while index < len(data) | 循环处理所有区间查询，直至输入数据读取完毕 |
res = prefix[b+1] - prefix[a] | 核心公式：区间[a,b]的和 = 前b+1个元素和 - 前a个元素和，O(1)时间计算 |
print(res) | 输出每个区间的计算结果 |