Elearning CodePath – CTP Online Judge

Cập Nhật và Truy Vấn Tổng Đoạn

SEG004

🟢 Medium #Segment Tree #Interval #Data Structure

### 📌 Thông tin chung

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

Cho dãy $A$ gồm $N$ phần tử và $Q$ truy vấn.

Có 2 loại truy vấn:

1.  **Cập nhật (Type 1):** Tăng giá trị tất cả các phần tử trong đoạn $[L, R]$ lên một lượng $W$.
    $    A_i \leftarrow A_i + W, \quad \forall i \in [L, R]$
2.  **Truy vấn (Type 2):** Tính **tổng giá trị** các phần tử trong đoạn $[L, R]$.
    $    \sum_{i=L}^{R} A_i$

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

* Dòng đầu chứa hai số nguyên dương $N$ (số phần tử) và $Q$ (số truy vấn).
* Dòng thứ hai chứa $N$ số nguyên dương $A_1, A_2, \dots, A_N$ là giá trị ban đầu của dãy.
* $Q$ dòng tiếp theo chứa truy vấn thuộc 1 trong 2 loại trên:
    * **Type 1:** Gồm `1 L R W`.
    * **Type 2:** Gồm `2 L R`.

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

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

Câu trả lời cho các truy vấn loại 2 (tổng giá trị đoạn $[L, R]$).

---
### ✨ Ví dụ

| Input | Output |
| :---: | :---: |
| `5 4` `1 2 3 4 5` `1 2 4 2` `2 3 5` `1 1 4 3` `2 1 5` | `16` `33` |

Giải thích ví dụ:
* $A$ ban đầu: $[1, 2, 3, 4, 5]$.
1.  **Thao tác `1 2 4 2`:** $A[2..4] \leftarrow A[i] + 2$.
    * $A$ mới: $[1, 2+2, 3+2, 4+2, 5] = [1, 4, 5, 6, 5]$.
2.  **Thao tác `2 3 5`:** Tính tổng $A[3..5]$.
    * $5 + 6 + 5 = 16$. Output: **16**.
3.  **Thao tác `1 1 4 3`:** $A[1..4] \leftarrow A[i] + 3$.
    * $A$ mới: $[1+3, 4+3, 5+3, 6+3, 5] = [4, 7, 8, 9, 5]$.
4.  **Thao tác `2 1 5`:** Tính tổng $A[1..5]$.
    * $4 + 7 + 8 + 9 + 5 = 33$. Output: **33**.

---
### 🏷 Phân tích và Ràng buộc

| Subtask | Ràng buộc |  Tỷ lệ điểm |
| :--- | :--- | :--- |
| $1$ | $N, Q \le 1000$ | $30\%$ |
| $2$ | $N, Q \le 10^5$ | $30\%$ |
| $3$ | $N, Q \le 10^5$ |  $40\%$ |

---

✅ Đã AC: 6 / 15 submissions