---
# System prepended metadata

title: Introductory problems

---

### Prefix Sum, Diff Array, Fenwick Tree
- [Dãy nghịch thế](https://oj.vnoi.info/problem/NKINV). Dùng Fenwick đánh dấu giá trị ($fenwick[x] =$ (số lượng vị trí đã duyệt qua có giá trị bằng $x$))
- Cho một dãy số nguyên dương $a_1,a_2,\cdots,a_n$ và số nguyên dương $D$. Đếm số cặp ($i,j$) ($1 \le i \le j \le n$) sao cho $|a_i - a_j| \ge D$. ($2 \le n \le 2 \times 10^5, 1 \le a_i,D \le n$). Giống câu trên.
- [Đoạn con có tổng lớn nhất](https://cses.fi/problemset/task/1643). Prefix Sum, No Fenwick.
- [Đếm số đoạn con không âm](https://marisaoj.com/problem/207). Fenwick Tree, Prefix Sum, **Nén số**.
- [C11SEG](https://oj.vnoi.info/problem/c11seq). Fenwick Tree, Nén số, xử lý $L,R$ như Prefix Sum.
-  [KSS](https://marisaoj.com/problem/390). Chặt nhị phân kết quả, Fenwick, Prefix Sum, Nén số. 

**Đã dạy đến đây**
-  [Trung bình cộng](https://marisaoj.com/problem/63), [Chia hết cho d](https://marisaoj.com/problem/62), [Xâu con tỉ lệ](https://marisaoj.com/problem/435)
-  [Nằm trong 1](https://marisaoj.com/problem/381), [Nằm trong 2](https://marisaoj.com/problem/380). Bài toán về đoạn trên trục số, Nén số.
---

### Sorting
Khi bài toán không quan trọng vị trí các phần tử (hoặc quan trọng nhưng dễ xử lý) (Không có query update,), sort lại thường cho ta nhiều insights thú vị (Giảm chiều DP, ...).

- Phần *Sắp xếp* của MarisaOJ.
- [Cạnh tam giác](https://marisaoj.com/problem/85)
- [K-query](https://marisaoj.com/problem/210). Sort lại query
- Cho dãy số nguyên dương $a_1,a_2,\cdots,a_n$ ($2 \le n, a_i \le 2 \times 10^5$). Tìm cặp vị trí ($i,j$) ($1 \le i < j \le n$) sao cho: $$S = |\{k \in (i,j) \mid \min(a[i], a[j]) \le a_k \le \max(a[i], a[j])\}|$$ đạt giá trị cực đại.