この記事では累積和と尺取り法を駆使することで解ける問題をPythonで実装していきます。それぞれのアルゴリズムについての説明はこの記事では省略しますが、別記事で解説していますので累積和と尺取り法についてまず知りたいという方は以下にリンクを載せて…

累積和とはその名の通り、累積の和をとる前処理をすることによってクエリの速度を上げることができるアルゴリズムです。実際に累積和の問題をPythonで解いていきます。どれくらい速くなるかを確認していきましょう。