Elearning CodePath – CTP Online Judge

Cập nhật 1 phần tử – Tính tổng đoạn

SUMQUERY

Đề bài

Cho dãy số nguyên $A = (A_1, A_2, \dots, A_n)$ gồm $n$ phần tử, các phần tử được đánh số từ $1$ đến $n$.

Cần thực hiện $q$ truy vấn thuộc một trong hai loại sau:

- `1 i x`: tăng giá trị của phần tử thứ $i$ thêm $x$ đơn vị, tức là:
$A_i \leftarrow A_i + x$

- `2 l r`: tính và in ra tổng các phần tử trên đoạn từ vị trí $l$ đến vị trí $r$, tức là:
$A_l + A_{l+1} + \dots + A_r$

Với mỗi truy vấn loại `2`, hãy in ra kết quả theo đúng thứ tự xuất hiện.

Dữ liệu vào

| Thành phần | Mô tả |
|---|---|
| Dòng 1 | Hai số nguyên $n, q$ |
| Dòng 2 | $n$ số nguyên $A_1, A_2, \dots, A_n$ |
| $q$ dòng tiếp theo | Mỗi dòng mô tả một truy vấn thuộc một trong hai dạng `1 i x` hoặc `2 l r` |

Ràng buộc

| Thành phần | Giới hạn |
|---|---|
| $1 \le n, q \le 10^5$ |  |
| $abs(A_i), abs(x) \le 10^9$ |  |
| $1 \le i \le n$ | với truy vấn loại `1` |
| $1 \le l \le r \le n$ | với truy vấn loại `2` |

Kết quả ra

| Thành phần | Mô tả |
|---|---|
| Với mỗi truy vấn loại `2` | In ra một dòng chứa tổng các phần tử trên đoạn $[l, r]$ |

Ví dụ

| Input | Output | Giải thích |
|---|---|---|
| `5 5` `1 2 3 4 5` `2 1 3` `1 2 10` `2 1 3` `1 5 -8` `2 4 5` | `6` `16` `1` | Ban đầu, tổng đoạn $[1,3]$ là $1+2+3=6$. Sau truy vấn `1 2 10`, ta có $A_2 \leftarrow 2+10=12$, nên mảng trở thành $(1,12,3,4,5)$. Khi đó tổng đoạn $[1,3]$ là $1+12+3=16$. Sau truy vấn `1 5 -8`, ta có $A_5 \leftarrow 5-8=-3$, nên tổng đoạn $[4,5]$ là $4+(-3)=1$. |
| `4 4` `7 7 7 7` `2 1 4` `1 3 -7` `2 2 4` `2 3 3` | `28` `14` `0` | Ban đầu tổng đoạn $[1,4]$ là $28$. Sau khi thực hiện truy vấn `1 3 -7`, mảng trở thành $(7,7,0,7)$. Khi đó tổng đoạn $[2,4]$ là $7+0+7=14$, còn tổng đoạn $[3,3]$ là $0$. |
| `3 5` `-1 -2 -3` `2 1 3` `1 1 4` `2 1 1` `1 3 10` `2 1 3` | `-6` `3` `8` | Ban đầu tổng đoạn $[1,3]$ là $-6$. Sau truy vấn `1 1 4`, mảng trở thành $(3,-2,-3)$ nên tổng đoạn $[1,1]$ là $3$. Sau truy vấn `1 3 10`, mảng trở thành $(3,-2,7)$ nên tổng đoạn $[1,3]$ là $8$. |

Subtask

| Subtask | Ràng buộc | Tỷ lệ điểm |
|---|---|---|
| 1 | $1 \le n, q \le 1000$ | 30% |
| 2 | Không có ràng buộc gì thêm | 70% |

✅ Đã AC: 5 / 7 submissions