Elearning CodePath – CTP Online Judge

Tổng với Cập nhật Tăng

INCSUMIT

🟢 Easy #Segment Tree #Fenwick Tree

### 📌 Thông tin chung

---
### 📝 Bài toán

Cho mảng $A$ gồm $N$ số nguyên, $A = (A_1, A_2, \dots, A_N)$.
Yêu cầu thực hiện $Q$ truy vấn trên mảng này. Mỗi truy vấn thuộc một trong hai loại sau:

* **Loại 1** (`1 u w`): Tăng giá trị của phần tử $A_u$ lên một lượng $w$.
    $  A_u \leftarrow A_u + w$
* **Loại 2** (`2 u v`): Tính tổng các phần tử trong đoạn $[u, v]$ của mảng.
    $  \text{Kết quả} = \sum_{i=u}^{v} A_i$

---
### 📥 Định dạng Đầu vào

Dữ liệu vào từ file `INCSUMIT.INP`:

* Dòng 1: Ghi số nguyên dương $N$.
* Dòng 2: Ghi $N$ số nguyên $A_1, A_2, \dots, A_N$ - mảng ban đầu.
* Dòng 3: Ghi số nguyên dương $Q$.
* $Q$ dòng cuối cùng: Mỗi dòng ghi một truy vấn theo quy cách mô tả ở trên.

Giới hạn:
* $1 \le N \le 10^5$.
* $1 \le Q \le 10^5$.
* $-10^9 \le A_i, w \le 10^9$.

---
### 📤 Định dạng Đầu ra

Ghi ra file `INCSUMIT.OUT`. Với các truy vấn loại 2, in ra kết quả tìm được trên một dòng riêng biệt.

---
### ✨ Ví dụ

| Input (`INCSUMIT.INP`) | Output (`INCSUMIT.OUT`) |
| :--- | :--- |
| `5` `1 1 1 1 1` `4` `1 2 4 6` `2 3 5` `1 3 5 -7` `2 3 4` | `15` `0` |

---
### 🏷 Subtask

| Subtask | Ràng buộc | Số điểm ước tính |
| :--- | :--- | :--- |
| 1 | $N, Q \le 5000$ | $40\%$ |
| 2 | $N, Q \le 10^5$ | $60\%$ |

---

✅ Đã AC: 0 / 0 submissions