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

0

nhatnam3004 9:46 p.m. 14 Tháng 11, 2024

how ac python?
help me pls

0

quan_vu2 9:16 p.m. 24 Tháng 10, 2024

1300pts thomw

#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

1

hjhjhjhjhj 8:59 a.m. 8 Tháng 4, 2024

include<bits/stdc++.h>

define int long long

using namespace std;
int a[1000001];
int st[4000001];
int n,k;
void build(int id,int l,int r)
{
if (l==r)
{
st[id]=a[l]; // fixed the index here
}
else
{
int mid=(l+r) >> 1;
build(id2,l,mid);
build(id2+1,mid+1,r);
st[id]=st[id2]+st[id2+1];
}
}
int get(int id,int l,int r,int u,int v)
{
if (u > r || v < l) return 0;
if (l >= u && r <= v) return st[id]; // changed l > u to l >= u
int mid =( l + r ) / 2;
int dp1 = get(id2,l,mid,u,v);
int dp2 = get(id2+1,mid+1,r,u,v); // fixed the index here
return dp1 + dp2;
}
signed main()
{
ios_base::sync_with_stdio(0);
cin.tie(0);cout.tie(0);
cin>>n>>k;
for (int i=1;i<=n;i++)
{
cin>>a[i];
}
build(1,1,n);
while (k--)
{
int u,v;
cin>>u>>v;
cout<<get(1,1,n,u,v)<<"\n";
}
}

0

hien18086 11:40 p.m. 7 Tháng 3, 2024

sol dành cho ai bí ý tưởng: https://ideone.com/aYll2J

1

dbthuan208 8:58 p.m. 18 Tháng 6, 2023

bài này prefix được mà :v

-7

hungtien2202 8:30 p.m. 9 Tháng 11, 2022

em làm được nhưng test 2 quá time ạ. Có cách nào để khắc phục không ạ

Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.