2次元配列の\(i\) 行目\(j\) 列目を\((i, j)\) という座標で表すことにします。
与えられた数列\(A\) に対し、\(1\)以上\(N\)以下の任意の整数\(i\)について\((i, A_{i})\) の値が\(A_{i}\) であり、それ以外の座標の値が\(0\) であるような2次元配列を考えます。
このとき、この問題の各クエリは、この2次元配列上の長方形の範囲にある値の総和を求める問題だと考えられます。
そのため、セグメント木の各ノードがセグメント木になっているようなデータ構造を用いれば、各クエリを\(O((\log N)^{2})\) で処理することができます。
ただし、セグメント木の各ノードであるセグメント木を完全に構成しようと思うとメモリも時間も足りないため、必要な場所だけ作るような工夫が必要です。

参考までに、この方針で提出したもののリンクを載せます。
https://atcoder.jp/contests/abc339/submissions/50001613