1 l r x の形式のクエリを加算クエリ、2 i x の形式のクエリを代入クエリと呼ぶことにします。

\(q\) 番目のクエリで \((i, j)\) の値を求めるとします。\(i\) 行目に対する代入クエリとしては、その時点で最新のものだけ考えればよいです。そのクエリが \(q'\) 番目であり、代入される値が \(x\) であるとすると、求めるべき値は次のようになります。

• \(x\) と \(q'+1, \dots, q\) 番目のクエリで \(j\) 列目に加算される値を足し合わせたもの。

\(1, 2, \dots, k\) 番目のクエリで \(j\) 列目に加算される値を \(S_{k, j}\) とおくと、\(x + S_{q, j} - S_{q', j}\) が答えとなります。

以上より \(S_{k, j}\) を求める問題に帰着されるので、以下の問題を解くことができればよいです。

• はじめに、数列 \(S\) を \(S = (0, \dots, 0)\) で初期化する。
• 以下の形式のクエリを処理する。
  • \(S_l, \dots, S_r\) に \(x\) を加算する。
  • \(S_j\) を出力する。

\(S\) ではなく \(S\) の差分を管理する問題に言い換えると次のようになります。

• はじめに、数列 \(S'\) を \(S' = (0, \dots, 0)\) で初期化する。
• 以下の形式のクエリを処理する。
  • \(S'_l\) に \(x\) を、\(S'_{r+1}\) に \(-x\) を加算する。
  • \(S'_1 + \dots + S'_j\) を出力する。

これはフェニック木と呼ばれるデータ構造を用いて効率的に解くことができます。実装には AtCoder Library の atcoder::fenwick_tree を用いると便利です。全体の計算量は \(O(N + M + Q \log M)\) となります。

実装例 (C++)