Elearning CodePath – CTP Online Judge

Dãy cộng đoạn

rangeadd

🟢 Easy #Difference Array #Fenwick Tree #Data Structure

Ban đầu có dãy `a` gồm `n` phần tử, tất cả bằng `0`.  
Có `q` thao tác thuộc một trong hai loại:

```text
1 l r x
```

Cộng `x` vào mọi phần tử từ `l` đến `r`.

```text
2 p
```

Hỏi giá trị hiện tại của `a[p]`.

## Input

```text
n q
q dòng tiếp theo, mỗi dòng là một thao tác
```

## Output

Với mỗi thao tác loại `2`, in ra giá trị được hỏi trên một dòng.

## Subtasks

| Subtask | Ràng buộc gợi ý | Điểm | Hướng làm |
|---|---:|---:|---|
| 1 | `n, q ≤ 200` | 20 | Mô phỏng |
| 2 | `n, q ≤ 5000` | 30 | Mảng hiệu nếu offline |
| 3 | `n, q` lớn | 50 | Fenwick Tree |

## Ví dụ

### Input

```text
5 7
1 1 3 4
2 2
1 2 5 -1
2 4
1 5 5 10
2 5
2 1
```

### Output

```text
4
-1
9
4
```

### Giải thích ví dụ

Sau thao tác `1 1 3 4`, dãy là:

```text
4 4 4 0 0
```

Nên truy vấn vị trí `2` cho kết quả `4`.

Sau thao tác `1 2 5 -1`, dãy là:

```text
4 3 3 -1 -1
```

Nên truy vấn vị trí `4` cho kết quả `-1`.

Sau thao tác `1 5 5 10`, dãy là:

```text
4 3 3 -1 9
```

Nên truy vấn vị trí `5` cho kết quả `9`, vị trí `1` cho kết quả `4`.

✅ Đã AC: 2 / 4 submissions