はじめに
タグにあるように，競技プログラミングを知っている前提でこの記事は書いてあります．知らなくても理解は出来ると思いますが，多少競プロに触れていた方がわかりやすいと思います．
[追記]私も2024年末で緑になったものなので、内容は浅いかもしれないです.
累積和とは
累積和とは，簡単に言うと「配列の最初から，現在見ている位置までの総和」という意味です．
考えやすいように問題を用意します．まず，こんな表があります．
ここで，単なる数字はお客さんの人数とします．
1/3から1/6までの合計客数はいくつでしょう，という問題が出たとしましょう．累積和について知らない方ならは「5+2+3+1=11」と計算をすると思います．
今回の場合はそれでも不都合がありません．
しかし，この年月の表が長かったり，複数の期間について質問された時に，毎回全部の期間について計算するのは，面倒で効率が悪いです．
これをプログラミングで実装する時，$N$を日数，$M$を与えられる期間の数とすると，$O(NM)$なので，日数$(N)$やクエリの数$(M)$によっては，競プロだとTLE(実行制限時間超過)する可能性があります．
ということで，累積和を使いましょう．上の表のようなものをプログラムで考えたいので，配列に入れます．
vector<int> customer = {0,10,1,5,2,3,1,8};
//最初の0は0日目，必要な理由も後でわかります．
累積和を使うため，1/1から現在見ている日数までの合計数を，現在見ている日数の場所に入れます．
vector<int> sumcustomer(8,0); //累積和の配列,同じく0日目あり．
for(int i=1;i<=8;i++){
sumcustomer[i] = sumcustomer[i-1] + customer[i];
}
/*
sumcustomerの中身は
sumcustomer = {0,10,11,16,18,21,22,30};
になります．
*/
こうすることで，sumcustomer[2]を見たら，1/1から1/2までの総和，sumcustomer[7]を見たら1/1から1/7までの総和がわかります．
Q:それはすごいけど，始点の日が変わった時の総和はわからないよ？
A:よく考えてみよう！
ここからが重要です．さっき言った1/3から1/6までをこのsumcustomerのみ利用して計算しましょう．
とは言っても簡単で，
『求める答え =「1/6までの総和」-「1/2までの総和」』となります．
イメージはこんな感じ．ちなみに，オーダー数は$O(M)$になるはず．
累積和を求めているので，配列の6番目から2番目を引くことで求められる．
区間がl,rで与えられるとします．($l=3，r=6$)
int l,r;
cin >> l >> r;//入力受け取り
cout << sumcustomer[r] - sumcustomer[l-1] << endl;
こうすることで，求める区間の総和がわかりました．
customerとsumcustomerの範囲を($N$(日数)$+1$)にしていたのは，$l=1,r=($範囲内の数字$)$と与えられていた時，つまり，1/r日目までの総和を求めたい時にも一般化したいからですね．0日目を用意することで，$l=1$の時に参照できる場所を作っています．
一応，問題として出てくる形式に書き換えておきます．
$N$日間に，それぞれお客さんが何人来たかが$A_1,A_2,・・・,A_N$で与えられます．この時，$M$個の期間$L,R$が与えられるので，それぞれの期間にお客さんが何人いたかを出力せよ．
($2 \leq N \leq 10^5$)，($2 \leq M \leq 10^5$)，($0 \leq A \leq 100$)，($1 \leq L < R \leq N$)
入力
$N$ $M$
$A_1,A_2,・・・,A_N$
$L_1,R_1$
$L_2,R_2$
・
・
・
$L_M,R_M$
入力(copyして使ってみてください)
7 1
10 1 5 2 3 1 8
3 6
上の入力に対する出力
11
自分の解答例
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
int main(){
int n,m;
int A[100001],sumA[100001];
int l[100001],r[100001];
cin >> n >> m;
for(int i=1;i<=n;i++){
cin >> A[i];
}
//累積和の作成
for(int i=1;i<=n;i++){
sumA[i] = sumA[i-1] + A[i];
}
for(int i=0;i<m;i++){
cin >> l[i] >> r[i];
}
for(int i=0;i<m;i++){
cout << sumA[r[i]] - sumA[l[i]-1] << endl; //l-1までを引くことに注意
}
}
これを一般化すると，『求めたい区間の総和 =「$r$までの総和」 - 「$l-1$までの総和」』という意味です．ちなみに，オーダー数は$O(N+M)$になるはず！
他の問題
せっかくなので，別の問題についても考えてみましょう．
$N$日間会議が行われています．$M$人の人がいて，それぞれ$L$日から$R$日までいるとします．訪れる人が全員いる時間はありますか？
$(2 \leq N \leq 10^5)$，$(2 \leq M \leq 10^5)$，$(1 \leq L < R < N)$
入力
$N$ $M$
$L_1$ $R_1$
$L_2$ $R_2$
・
・
・
$L_M$ $R_M$
という問題です．
今回の例では，
10日間あって，3人訪れる人がいる．
そのそれぞれの人が，
- 2日目から5日目
- 3日目から7日目
- 5日目から9日目
この期間で会議に出席しているとします．
入力
10 3
2 5
3 7
5 9
出力
Yes
(YesかNoでお答えください．)
ちなみに，問題のイメージとしてはこんな感じ．山になっているところの高さがMと同じになれば，Yesを出力することになる．(端が含まれることに注意)
vector<int> hitorime = {0,0,1,1,1,1,0,0,0,0,0};
vector<int> hutarime = {0,0,0,1,1,1,1,1,0,0,0};
vector<int> 3ninnme = {0,0,0,0,0,1,1,1,1,1,0};
//0日目あり，10+1で配列を作成
会議に出席している日を1，出席していない日を0とすると，こんな感じ．
これを言い換えると，「L日目からR日目まではいて，R+1日目からはいない」ということになります．
「上記の配列を累積和で作られた配列にしたい」時，累積和にする前の配列を考えると，下のようになります．
bef1 = {0,0,1,0,0,0,-1,0,0,0,0};//hitorime
bef2 = {0,0,0,1,0,0,0,0,-1,0,0};//hutarime
bef3 = {0,0,0,0,0,1,0,0,0,0,-1};//3ninnme
それぞれのbefに対して累積和の計算をしてみると上のhitorimeなどの配列と同じ値になると思います．
まとめると，「前日比の人数を記録したら，どの日に何人いたかわかる」ということです．
ということで，さっきの問題を解いてみるとこんな感じになると思います．前日比なので累積和にする前の配列はまとめちゃって大丈夫．
#include <bits/stdc++.h>
using namespace std;
int main(){
int n,m;
int l[101],r[101]; //会議に来る人の種類を100人としてます．
cin >> n >> m;
vector<int> zenjituhi(n+1); //一つ多めにとって0日目からn日目まで
vector<int> sumPeople(n+1);
for(int i=1;i<=m;i++){ //m人の情報が与えられる
cin >> l[i] >> r[i];
zenjituhi[l[i]]++;
zenjituhi[r[i+1]]--;//(いなくなるのはr+1日目なので注意)
}
for(int i=1;i<=n;i++){
sumPeople[i] = sumPeople[i-1] + zenjituhi[i];
}
bool ok = false; //該当する日があるかどうか
for(int i=0;i<=n;i++){
if(sumPeople[i] == m){
ok = true;
break;
}
}
cout << (ok ? "Yes" : "No") << endl;
}
ちなみに，この問題の制約の$(1 \leq L < R < N)$が$(1 \leq L < R \leq N)$になった場合，
zenjituhi[r[i+1]]--;//(いなくなるのはr+1日目なので注意)
この部分で配列範囲外を参照する可能性があります．
配列サイズを(n+2)にしておくか，
int zenjituhi[100100];
のように，ある程度大きめに取っておくと安全です．(こっちは個人的にはそこまで好きではないです)
最後に
この累積和，実は二次元にも広げられます(二次元累積和)．気が向いたら二次元累積和についても書きます.