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

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

Hiếu Nguyễn

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

Please read the guidelines before commenting.

0
congtyluuthaibao1978 đã bình luận lúc 28, Tháng 11, 2025, 4:44
include <bits/stdc++.h>

using namespace std; using ll = long long;

struct Fenwick { int n; vector<ll> f; Fenwick(int n): n(n), f(n+1, 0) {} void update(int i, ll delta) { for (; i <= n; i += i & -i) f[i] += delta; } ll query(int i) { ll s = 0; for (; i > 0; i -= i & -i) s += f[i]; return s; } ll range_query(int l, int r) { return query(r) - query(l-1); } };

int main() { ios::syncwithstdio(false); cin.tie(nullptr);

int n, Q; cin >> n >> Q; Fenwick bit(n); for (int i = 1; i <= n; i++) { ll x; cin >> x; bit.update(i, x); } while (Q--) { int type; cin >> type; if (type == 1) { int i; ll x; cin >> i >> x; bit.update(i, x); } else { int u, v; cin >> u >> v; cout << bit.range_query(u, v) << " "; } } return 0;

}

segment tree

#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
const ll maxn = 1e5;
ll n, q, a[maxn + 5], t[maxn * 4 + 5];
void build(ll v,ll l, ll r) {
    if(l == r) {
        t[v] = a[l];
        return;
    }
    ll m = (l + r) / 2;
    build(2 * v, l, m);
    build(2 * v + 1, m + 1, r);
    t[v] = t[2 * v] + t[2 * v + 1];
}
void update(ll v, ll l, ll r, ll pos, ll val) {
    if(l == r) {
        t[v]+=val;
        return;
    }
    ll m = (l + r) / 2;
    if(pos <= m) {
        update(2 * v, l, m, pos, val);
    }
    else {
        update(2 * v + 1, m + 1, r, pos, val);
    }
    t[v] =  t[2 * v] + t[2 * v + 1];
}
ll query(ll v, ll tl, ll tr, ll l, ll r) {
    if(tl > r || tr < l) return 0;
    if(l <= tl && r >= tr) return t[v];
    ll m = (tl + tr) / 2;
    ll s1 = query(2 * v, tl, m, l, r);
    ll s2 = query(2 * v + 1, m + 1, tr, l, r);
    return s1 + s2;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> a[i];
    build(1,1,n);
    while(q--) {
        int type;
        ll i,j;
        cin >> type >> i >> j;
        if(type == 1) update(1,1,n,i,j);
        else cout << query(1,1,n,i,j) << ' ';
    }
    return 0;
}