CSES - Static Range Sum Queries | Truy vấn tổng mảng tĩnh
Xem PDF
Đ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
11
2
24
4
Bình luận
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";
}
}
sol dành cho ai bí ý tưởng: https://ideone.com/aYll2J
bài này prefix được mà :v
Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.