https://atcoder.jp/contests/s8pc-1/submissions/15582396 半開区間はデータの境界を表す 制約から1個のクエリを未満で処理する必要がある。街Aから街Bへ移動するとき移動距離は半開区間[A, B)で表される。したがって、半開区間そのまま累積和で加算処理し…

http://judge.u-aizu.ac.jp/onlinejudge/review.jsp?rid=4728976 繰り返し二乗法を使うと累乗は mのn乗をするのにn回だけ掛け算するのは制約からTLEする。 二乗した値を二乗することで木構造と同じ理由でで計算できるようになる。