【模板】静态区间和（前缀和）
时间限制：5秒 空间限制：512M
网页链接
牛客tracker
牛客tracker & 每日一题，完成每日打卡，即可获得牛币。获得相应数量的牛币，能在【牛币兑换中心】，换取相应奖品！助力每日有题做，丰盈牛币日益多！
题目描述
对于给定的长度为n nn的数组{ a 1 , a 2 , … , a n } \{ a_1,a_2,…,a_n \}{a1,a2,…,an}，你需要构建一个能够维护区间和信息的数据结构，使得其能支持：
- 区间和查询：输出[ l , r ] [l,r][l,r]这个区间中的元素之和，即∑ i = l r a i ∑_{i=l}^ra_i∑i=lrai。
输入描述：
第一行输入两个整数n , q ( 1 ≦ n , q ≦ 10 6 ) n,q(1≦n,q≦10^6)n,q(1≦n,q≦106)代表数组中的元素数量、操作次数。
第二行输入n nn个整数a 1 , a 2 , … , a n ( − 10 9 ≦ a i ≦ 10 9 ) a_1,a_2,…,a_n(−10^9≦a_i≦10^9)a1,a2,…,an(−109≦ai≦109)代表初始数组。
此后q qq行，每行输入两个整数l , r ( 1 ≦ l ≦ r ≦ n ) l,r(1≦l≦r≦n)l,r(1≦l≦r≦n)代表区间和查询。
输出描述：
对于每一次询问，输出一行一个整数代表区间和。
示例1
输入：
3 2 1 2 4 1 2 2 3输出：
3 6解题思路
本题是前缀和经典模板题，核心是通过O ( n ) O(n)O(n)预处理前缀和数组，将每次区间和查询的时间复杂度降至O ( 1 ) O(1)O(1)；首先读取数组长度n nn和查询次数q qq，初始化下标从1 11开始的前缀和数组（q [ 0 ] = 0 q[0]=0q[0]=0），遍历原数组时将每个元素累加到前缀和数组中（q [ i ] = q [ i − 1 ] + a [ i ] q[i] = q[i-1] + a[i]q[i]=q[i−1]+a[i]），利用l o n g longlongl o n g longlong类型存储避免因元素值范围（− 1 e 9 ˜ 1 e 9 -1e9 \~\ 1e9−1e9˜1e9）和n nn达1 e 6 1e61e6导致的数值溢出；对于每次区间查询[ l , r ] [l,r][l,r]，直接计算前缀和数组的q [ r ] − q [ l − 1 ] q[r] - q[l-1]q[r]−q[l−1]得到区间和并输出；该方法总时间复杂度为O ( n + q ) O(n+q)O(n+q)，无冗余计算，完美适配 $n、q≤1e6的规模，高效且精准完成所有区间和查询操作。
代码内容
#include<bits/stdc++.h>usingnamespacestd;typedeflonglongll;typedefunsignedlonglongull;typedefpair<ll,ll>pii;constll p=1e9+7;constll N=1e5+10;signedmain(){ll n,t;cin>>n>>t;vector<ll>q(n+1,0);for(ll i=1;i<=n;i++){cin>>q[i];q[i]+=q[i-1];}while(t--){ll l,r;cin>>l>>r;cout<<q[r]-q[l-1]<<endl;}return0;}
)
)
