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

View as PDF
Submit solution
Points: 2.00 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
Hieu Nguyen
Problem types
Allowed languages
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

Comments

Please read the guidelines before commenting.


  • 0
    MisolHo  commented on March 13, 2025, 3:44 a.m. ← edited

    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;

    }