SegTree - segment tree

解説を見る
  • 実行時間制限：2000 ms
  • メモリ制限：1073741824 Bytes
  • 配点：100 点
  • ジャッジ：Batch
  • 使用可能言語：All Batch Languages (dc (GNU dc), C++ (gcc), C (gcc), Python3 (CPython), Text (cat), Bash, Brainfuck, codon)

長さ NN の数列 AA があります。以下のクエリを処理してください。

  1. ApA_p を xx に変更する。
  2. l≤i<rl \leq i < r をみたす ii について、 AiA_i の和を出力する。
    QQ 個のクエリが与えられます。

制約

  • N=1024N = 1024
  • 0≤Ai≤1000  (1≤i≤N)0 \leq A_i \leq 1000 \; (1 \leq i \leq N)
  • 1≤Q≤10001 \leq Q \leq 1000
    • クエリ 1 について、1≤p≤N,  0≤x≤10001 \leq p \leq N, \; 0 \leq x \leq 1000
    • クエリ 2 について、1≤l<r≤N+11 \leq l < r \leq N + 1

入力

NN


A1 A2 ... ANA_1~A_2~...~A_N


QQ


query1query_1


query2query_2


⋮\vdots


queryQquery_Q

各 queryquery は以下のように与えられます。

  • 1 の場合：
1 p x1~p~x
  • 2 の場合：
2 l r2~l~r

出力

クエリ 2 の答えを順番に出力してください。

入出力例

入力例

8
1 2 4 2 5 0 0 0
3
2 1 4
1 2 3
2 1 6

出力例

7
15

このケースは N=1024N = 1024 を満たさないことに注意してください。