Editorial for Dòng chảy lặng thầm

Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Gợi ý 1 - Xử lý truy vấn mà không cộng lại cả đoạn

Nếu mỗi truy vấn đều duyệt từ l đến r, một đoạn dài có thể bị cộng đi cộng lại nhiều lần. Hãy tính trước thông tin cho mọi tiền tố của mảng.

Gợi ý 2 - Tổng tiền tố

Đặt prefix[i] là tổng các phần tử từ vị trí 1 đến i, và prefix[0] = 0. Khi đó tổng đoạn [l,r] bằng prefix[r] - prefix[l-1].

Lời giải đầy đủ

Ý tưởng

Đọc mảng và tạo mảng tổng tiền tố. Mỗi truy vấn chỉ cần lấy hiệu của hai tổng tiền tố. Vì các phần tử có thể âm và tổng có thể lớn, dùng long long.

Độ phức tạp

Tiền xử lý mất O(N); mỗi truy vấn mất O(1). Tổng thời gian O(N+Q), bộ nhớ O(N).

Code C++17

#include <bits/stdc++.h>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, q;
    cin >> n >> q;

    vector<long long> prefix(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        long long value;
        cin >> value;
        prefix[i] = prefix[i - 1] + value;
    }

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

    return 0;
}