Truy vấn tổng đoạn con - LCOJ: Luyen Code Online

QSUM - Truy vấn tổng đoạn con

Điểm: 2,00 (OI)

Giới hạn thời gian: 1.0s

Giới hạn bộ nhớ: 256M

Tác giả:

Hieu Nguyen

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, 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

Hãy đọc nội quy trước khi bình luận.

MisolHo đã bình luận lúc 13, Tháng 3, 2025, 3:44 ← chỉnh sửa →

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);

int n, q;
cin >> n >> q;
vector<int> a(n);
for (int i = 0; i < n; i++) cin >> a[i];

vector<int> pre(n, 0);
pre[0] = a[0];
for (int i = 1; i < n; i++) {
    pre[i] = pre[i - 1] + a[i];
}

while (q--) {
    int t; cin >> t;
    if (t == 1) {
        int p, x; cin >> p >> x;
        a[p - 1] += x;  
        for (int i = p - 1; i < n; i++) {
            pre[i] += x;
        }
    } else {
        int u, v;
        cin >> u >> v;
        cout << (u == 1 ? pre[v - 1] : pre[v - 1] - pre[u - 2]) << '\n';
    }
}

return 0;

}