たのしく累積和 : 競プロ典型 90 問 010 - Score Sum Queries（★2）
問題
学生がN人います．各学生の所属するクラス(1 or 2)と試験の成績が与えられます．
校長先生からQ回，次の質問がくるのでうまく答えたいです．
校長先生「L番目からR番目の学生の期末試験の点数の合計をクラス別で教えてくれ」
解説
制約を見ると質問は最大で100000回来るようです．そこで想定される最悪ケースの質問「全員の学生の期末試験の点数の合計をクラス別で教えてくれ」の計算量を考えます．
愚直に実装すると，1度の質問でO(N)かかります．学生は最大100000人いるみたいなので，100000 × 100000 > 1012 となり，コンピュータでは太刀打ちできません．高速化が必要です．
期末試験の点数の合計を高速に求められるととても嬉しいです．そこで，次の2つの配列を質問に答える前にあらかじめ用意しておきます．．
- cl[1][i] : 学籍番号i番目までの1クラスに所属する成績の総和
- cl[2][i] : 学籍番号i番目までの2クラスに所属する成績の総和
これを用いることで，高速にLからRまでの成績の総和を求めることができます．具体的には1クラスの場合，cl[1][R] - cl[1][L-1]で求めることができます(当然配列外参照などは気にする必要があります)．
これは累積和というテクニックです．これを用いることで1度の質問をO(1)で答えることができます．
累積和は色々なところで使うので，慣れる必要があります．
