洛谷P8218 【深进1.例1】求区间和 考点：一维前缀和

题目

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

核心思路

一维前缀和模板题

代码

可以让AI总结一下代码逻辑

这段代码实现了一维前缀和算法，用于高效解决区间求和问题。主要逻辑如下：

1. 预处理 (数据输入与求和)：
   • 读取数组长度 n。
   • 在读取每个元素 a[i] 的同时，计算前缀和 sum[i]，其中sum[i] = sum[i-1] + a[i]。这样sum[i]存储的是前 ii 个元素的总和。
2. 区间查询：
   • 读取查询次数 m。
   • 对于每次查询的区间 [l,r]，利用公式sum[r] - sum[l-1]在 O(1) 时间内计算出该区间内所有元素的和并输出。
3. 性能优化：
   • 使用ios::sync_with_stdio(0), cin.tie(0)加速输入输出，适用于大数据量的竞赛题目。

该算法将 m 次查询的总时间复杂度从 O(n×m) 降至 O(n+m)。

#include<bits/stdc++.h> using namespace std; #define endl '\n' const int N=1e5+5; int a[N]; int sum[N]; void solve(){ int n; cin>>n; for(int i=1;i<=n;i++){ cin>>a[i]; sum[i]=sum[i-1]+a[i]; } int m; cin>>m; for(int i=0;i<m;i++){ int l,r; cin>>l>>r; cout<<sum[r]-sum[l-1]<<endl; } } int main(){ ios::sync_with_stdio(0),cin.tie(0); int t=1; // cin>>t; while(t--) solve(); return 0; }