CSES - Static Range Sum Queries | Truy vấn tổng mảng tĩnh

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Pypy 3 2.0s

Python 3 4.0s

Tác giả:

Flower_On_Stone , NguyễnAnhQuốc_83

Dạng bài

Điểm: 1300 (p) Thời gian: 1.0s Bộ nhớ: 512M Input: bàn phím Output: màn hình

Cho một mảng gồm \(n\) số nguyên, nhiệm vụ của bạn là xử lý \(q\) truy vấn có dạng: tổng các phần tử trong đoạn [\(a, b\)] là bao nhiêu?

Input

Dòng đầu tiên là hai số nguyên \(n\) và \(q\): số phần tử và truy vấn.
Dòng thứ hai là \(n\) số nguyên \(x_1, x_2,\ldots, x_n\): các phần tử của mảng.
\(q\) dòng cuối cùng là các truy vấn. Mỗi dòng là hai số nguyên \(a\) và \(b\): tổng các phần tử trong đoạn \([a, b]\) là bao nhiêu?

Output

In ra đáp án của mỗi truy vấn.

Constraints

\(1 \le n, q \le 2 \cdot 10^5\)
\(1 \le x_i \le 10^9\)
\(1 \le a \le b \le n\)

Example

Sample input

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

Sample output

Bình luận

#include <bits/stdc++.h>
#define ll long long
const int N=1e6+3;
using namespace std;
int n,a[N],q;
ll s[N];
string st;
int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(NULL);
    cin >> n >> q;
    for(int i=1;i<=n;i++)
    {
        cin >> a[i];
        s[i]=s[i-1]+a[i];
    }
    while(q--)
    {
        int l,r;
        cin >> l >> r;
        cout << s[r]-s[l-1] << '\n';
    }
    return 0;
}

-Code này dùng tổng cộng dồn
-Không cần phức tạp gì nhiều

6 bình luận nữa