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

    }