QSUM - Truy vấn tổng đoạn con
Xem dạng PDF
Gửi bài giải
Điểm:
2,00 (OI)
Giới hạn thời gian:
1.0s
Giới hạn bộ nhớ:
256M
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift
Cho dãy số nguyên gồm ~n~ phần tử ~a_1, a_2, …, a_n~ và ~Q~ truy vấn. Mỗi truy vấn có một trong hai dạng:
- Dạng ~1:1\ i\ x:~ cộng vào số ở vị trí ~i~ giá trị ~x~ (tức là ~a_i = a_i + x~);
- Dạng ~2:2\ u\ v:~ Tìm tổng các số trong đoạn ~[u, v]~ (tức là tổng ~a_u + a_{u + 1} + … + a_v~).
Input
- Dòng đầu chứa hai số nguyên dương ~n~ và ~Q~;
- Dòng thứ hai chứa ~n~ số nguyên ~a_1, a_2, …, a_n~;
- ~Q~ dòng tiếp theo, mỗi dòng là ~3~ số nguyên mô tả một truy vấn.
Hai số liên tiếp trên một dòng được ghi cách nhau ít nhất một dấu cách.
Giới hạn:
- ~1 ≤ n ≤ 10^5; 1 ≤ u ≤ v ≤ n; 1 ≤ Q ≤ 10^5; |x|, |a_i| ≤ 10^4~.
Output
- Ghi trên một dòng nhiều số nguyên, mỗi số là câu trả lời cho truy vấn loại ~2~ (theo đúng thứ tự thực hiện các truy vấn), hai số liên tiếp ghi cách nhau một khoảng trắng.
Sample
Input #1
5 3
2 -1 5 3 -3
2 1 4
1 3 2
2 2 5
Output #1
9 6
Problem source: Chuyên Sơn La Online Judge
Bình luận
int n, q, a[100003], t[400003]; void build (int v, int l, int r) { if (l == r) t[v] = a[l]; else { int mid = (l + r) / 2; build(2 * v, l, mid); build (2 * v + 1, mid + 1, r); t[v] = t[2v] + t[2v+1]; } } void update (int v, int l, int r, int pos, int val) { if (l == r) t[v] += val; else { int mid = (l + r) / 2; if (pos <= mid) update(2v, l, mid, pos, val); else update(2v+1, mid + 1, r, pos, val); t[v] = t[2v] + t[2v+1]; } } int querry (int v, int l, int r, int tl, int tr) { if (tl > tr) return 0; if (l == tl && r == tr) return t[v]; else { int mid = (l + r) / 2; int s1 = querry(2v, l, mid, tl, min(tr, mid)); int s2 = querry(2v+1, mid + 1, r, max(tl, mid + 1), tr); return s1 + s2; } } int main() { cin >> n >> q; for (int i = 1; i <= n; ++i) cin >> a[i]; build(1, 1, n);
for (int i = 1; i <= q; ++i) { int loai; cin >> loai; if (loai == 1) { int pos, val; cin >> pos >> val; update(1, 1, n, pos, val); } else { int l, r; cin >> l >> r; cout << querry(1, 1, n, l, r) << ' '; } } return 0;
}
include <bits/stdc++.h>
using namespace std; using ll = long long; const int MOD = (int)1e9+7;
int main() { ios::syncwithstdio(false); cin.tie(nullptr); cout.tie(nullptr);
}