Static Range Sum Queries

Static Range Sum Queries
CSES medium

تم إعطاؤك مصفوفة من \(n\) أعداد صحيحة و \(q\) استفسارات. كل استفسار يطلب مجموع القيم في النطاق الشامل \([a,b]\). اطبع الإجابة لكل استفسار.

Solution

قم بحساب المجاميع التراكمية (prefix sums) مسبقًا بحيث يمكن الإجابة عن أي استعلام نطاق في زمن \(O(1)\).

لتكن \(S[0]=0\) ولـ \(i\ge1\)، يكون \(S[i]=S[i-1]+x_i\).

بعد ذلك، لأي استعلام \([a,b]\) (مؤشرات تبدأ من 1)، يكون المجموع:

\[ \text{sum}(a,b)=S[b]-S[a-1]. \]

بناء \(S\) يستغرق \(O(n)\)؛ والإجابة عن جميع الاستفسارات تستغرق \(O(q)\).

Noteالمجاميع التراكمية (مؤشرات تبدأ من 1)

  • يتم البناء مرة واحدة: \(S[i] = S[i-1] + x_i\) لكل \(i = 1..n\)

  • الاستعلام: \(S[b] - S[a-1]\)

    :::

#include <iostream>
#include <vector>
using namespace std;

int main() {
    int n, q;
    cin >> n >> q;

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

    while (q--) {
        int a, b;
        cin >> a >> b;          // نطاقات تبدأ من 1
        cout << (pref[b] - pref[a - 1]) << '\n';
    }
}
Cautionالمجاميع 64-بت

يمكن أن تصل القيم إلى \(2\cdot10^5 \times 10^9 = 2\cdot10^{14}\)، لذلك احفظ المجاميع التراكمية والنتائج في long long.