# **Vấn đề**
[CSES - Static Range Sum Queries](https://cses.fi/problemset/task/1646)
Cho mảng $A$ gồm $n$ số được đánh số từ $1 \rightarrow n$. Trả lời $q$ truy vấn $l, r$ hỏi tổng trong đoạn $[l, r]$ là bao nhiêu.
## Input
- Dòng đầu ghi $n, q$ là số lượng số trong mảng $A$ và số lượng truy vấn $(n, q \le 2.10^5)$
- <p>Dòng tiếp theo ghi $n$ số $a_1, a_2, ..., a_n$.</p>
- $q$ dòng sau, mỗi dòng ghi 2 số $l,r$
## Output
- Gồm $q$ dòng, mỗi dòng ghi kết quả của truy vấn $l_i, r_i$
## Ví dụ
### Input

6 3
2 3 4 5 1 8
1 4
3 6
2 5

### Output

14
18
13

# Ý tưởng ngây thơ
- Theo 1 ý nghĩ thông thường, đề bảo gì làm đó. Nghĩa là với mỗi truy vấn $l_i, r_i$ chúng ta sẽ duyệt $l \rightarrow r$ và cộng $a_i$ lại rồi in ra kết quả
- Cài đặt như sau

while (q--) {
    int l, r; cin >> l >> r;
    long long ans = 0;
    for (int i = l; i <= r; i++) {
        ans += a[i];
    }
    cout << ans << endl;
}

- Độ phức tạp cho ý tưởng ngây thơ trên sẽ là $O(n.q)$
- Thế nhưng với giới hạn trên thì ý tưởng trên có vẻ là bất khả thi trong giới hạn $1s$.

# Nhận xét
- Với giới hạn lớn như trên chúng ta có thể xây dựng 1 thuật toán chạy $O(n + q)$ trở xuống.
- Dễ nhận thấy rằng việc tính đi tính lại vòng for $l$ $\rightarrow$ $r$ là không cần thiết. Vậy câu hỏi đặt ra rằng liệu chúng ta có thể xây dựng trước toàn bộ tổng $l, r$ trên hay không?
- Gọi $S(i)$ là tổng các số trong đoạn từ $1 \rightarrow i$. Vậy ta muốn tính tổng trong đoạn từ $l \rightarrow r$, ta có công thức sau: $S(l...r) = S(r) - S(l - 1)$
- Để dễ hình dung công thức này ta có hình vẽ như sau:


- Vậy để xây dựng tổng từ $1 \rightarrow i$ ta có công thức như sau: $S[i] = S[i - 1] + a[i]$
- Với $S[i-1]$ là tổng từ $1 \rightarrow i - 1$ đằng trước và khi thêm $a[i]$ vào cuối.

# Ý tưởng tối ưu
- Với toàn bộ các nhận xét trên, chúng ta có thể viết vô cùng dễ dàng với code như sau:

//preprocess
for (int i = 1; i <= n; i++) {
    S[i] = S[i-1] + a[i];
}

while (q--) {
    int l, r; cin >> l >> r;
    cout << S[r] - S[l - 1] << endl;
}

- Tiền xử lí mảng $S$: $O(n)$
- Trả lời $q$ truy vấn: $O(q)$
- Tổng độ phức tạp: $O(n + q)$
# Bài tập áp dụng
[CSES - Maximum Subarray Sum](https://cses.fi/problemset/task/1643)
## Tóm tắt
Cho mảng $A$ gồm $n$ phần tử. Tìm mảng con liên tiếp khác rỗng có tổng lớn nhất. $(1 \le n \le 2.10^5, |a_i| \le 10^9)$
### Input

8
-1 3 -2 5 3 -5 2 2

### Output

9

### Giải thích
Chọn đoạn $[3, -2, 5, 3]$

## Lời giải

- Bài này là 1 bài kinh điển áp dụng [thuật toán Kadane](https://www.geeksforgeeks.org/largest-sum-contiguous-subarray/). Thế nhưng trong giới hạn bài viết chúng ta sẽ dùng prefix sum để giải bài này.
- Như bên trên, chúng ta sẽ xây dựng $S[i]$ là tổng các số trong đoạn từ $1 \rightarrow i$
- Vậy theo đề yêu cầu chúng ta sẽ cần tìm 1 đoạn $l, r$ trong mảng $A$ sao cho tổng là lớn nhất. Dễ nhận thấy bằng phương pháp tham lam, giả sử $r$ cố định, chúng ta sẽ muốn tìm $S(l - 1)$ thấp nhất. Bởi vì khi $S(l - 1)$ thấp nhất, thì $S(r) - S(l - 1)$ sẽ là lớn nhất. Chúng ta có thể viết bài toán lại theo công thức sau:
$ans_r = max(S(r) - S(l - 1))$
$ans_r = S(r) + max(-S(l - 1))$
$ans_r = S(r) - min(S(l - 1))$
- Vậy chúng ta có thể giải bài này bằng $O(n)$ như sau:

for (int i = 1; i <= n; i++) S[i] = S[i-1] + a[i];
long long m = INF; // INF = 1e18
long long ans = -INF;
for (int r = 0; r <= n; r++) {
    ans = max(ans, S[r] - m);
    m = min(m, S[r]);
}
cout << ans << endl;

# Bài tập thêm
- [CSES - Subarray Sums II](https://cses.fi/problemset/task/1661)
- [CSES - Subarray Divisibility](https://cses.fi/problemset/task/1662)
- [Atcoder - GCD on Blackboard](https://atcoder.jp/contests/abc125/tasks/abc125_c)
- [VNOJ - NKSEQ](https://oj.vnoi.info/problem/nkseq)
- [CF - Good Subarrays](https://codeforces.com/contest/1398/problem/C)