85. 一維陣列區間加值區間查詢總和

一維陣列區間加值區間查詢總和

• 給你一個一維陣列，你有兩個操作可以做：增加某一區間的值和求一個區間的總和
• 小心TLE

輸入說明:

• 輸入的第一行會有一個正整數$n$($1 \leq n \leq 1000000$)，表示給定陣列$S$的大小是$n$
• 陣列索引值編號從1開始
• 接著會有一行，有$n$個int範圍的整數，第$i$個整數代表陣列$S[i]$的值
• 接著有一個整數$t$($0<t \leq 100000$)，表示接下來有$t$個指令要執行
• 指令有兩種:
  • 1 x y c：將$S[x] \sim S[y]$的值增加c，c為int範圍，$1 \leq x \leq y \leq n$
  • 2 x y：查詢區間$S[x] \sim S[y]$中其元素總和，$1 \leq x \leq y \leq n$

輸出說明

• 對於每個2開頭的指令，請輸出查詢的結果，記得換行

範例輸入:

5
1 2 3 4 5
15
1 1 5 3
2 1 1
2 2 2
2 3 3
2 4 4
2 5 5
1 1 2 2
1 3 5 -1
2 1 5
2 1 4
2 1 3
1 2 4 9
2 2 4
2 1 4
2 3 4

範例輸出:

4
5
6
7
8
31
24
18
45
51
29

配分:

配分	限制
20%	$1 \leq n \leq 100$
20%	$1 \leq n \leq 1000$
60%	沒有限制
時限	350ms
記憶體	31447232 kb

Judge Setting

run-time limit: 350 ms
memory limit: 31447232 byte
測資數量: 0