Tổng tiền tố (Prefix Sum)

Tạo mảng pref[i] = pref[i-1] + a[i]. Khi đó tổng đoạn từ L đến R được tính trong O(1): pref[R] - pref[L-1].

C++

vector pref(n + 1, 0);
for (int i = 1; i <= n; i++) pref[i] = pref[i-1] + a[i];
long long sumLR = pref[r] - pref[l-1];

Python

pref = [0] * (n + 1)
for i in range(1, n + 1):
    pref[i] = pref[i-1] + a[i-1]
sumLR = pref[r] - pref[l-1]