Elearning CodePath – CTP Online Judge

PREFIXSUMMOD

🟢 Medium #Fenwick Tree

Đề bài

Cho dãy số nguyên $A = (A_1, A_2, \dots, A_n)$ gồm $n$ phần tử.

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

- `1 i x`: gán giá trị của phần tử thứ $i$ thành $x$, tức là $A_i \leftarrow x$.
- `2 l r`: tính tổng các phần tử từ vị trí $l$ đến vị trí $r$: $A_l + A_{l+1} + \dots + A_r$
và in ra kết quả theo modulo $10^9 + 7$.

Với mỗi truy vấn loại `2`, hãy in ra đáp án theo thứ tự xuất hiện.

Quy ước modulo

Gọi:

$M = 10^9 + 7$

Do các phần tử của mảng có thể âm, kết quả của mỗi truy vấn loại `2` phải được in dưới dạng một số nguyên trong đoạn từ $0$ đến $M-1$, tức là giá trị:

$\left( \sum_{k=l}^{r} A_k \right) \bmod M$

sau khi đã chuẩn hóa về không âm.

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 là tổng trên đoạn $[l, r]$ theo modulo $10^9 + 7$ |

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` `14` `1000000003` | Truy vấn 1: tổng đoạn $[1,3]$ là $1+2+3=6$. Sau truy vấn 2, mảng thành $(1,10,3,4,5)$. Truy vấn 3: tổng đoạn $[1,3]$ là $1+10+3=14$. Sau truy vấn 4, mảng thành $(1,10,3,4,-8)$. Truy vấn 5: tổng đoạn $[4,5]$ là $4+(-8)=-4$, in theo modulo là $10^9+7-4=1000000003$. |
| `4 4` `7 7 7 7` `2 1 4` `1 3 0` `2 2 4` `2 3 3` | `28` `14` `0` | Ban đầu tổng đoạn $[1,4]$ là $28$. Sau khi gán $A_3=0$, mảng thành $(7,7,0,7)$. Khi đó tổng đoạn $[2,4]$ là $14$, còn tổng đoạn $[3,3]$ là $0$. |
| `3 3` `-1 -2 -3` `2 1 3` `1 2 5` `2 1 3` | `1000000001` `1` | Ban đầu tổng đoạn $[1,3]$ là $-6$, in theo modulo là $1000000001$. Sau khi gán $A_2=5$, mảng thành $(-1,5,-3)$, tổng đoạn $[1,3]$ là $1$. |

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: 4 / 6 submissions