Point Update Range Query

Xem dạng PDF
Gửi bài giải
Điểm: 0,07 (OI)
Giới hạn thời gian: 1.0s
Giới hạn bộ nhớ: 256M
Input: stdin
Output: stdout
Dạng bài
Ngôn ngữ cho phép
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

Cho dãy ~x~ gồm ~n~ số nguyên, bạn cần thực hiện ~q~ truy vấn có một trong hai dạng sau:

  • ~1\ k\ u~: Cập nhật giá trị ở vị trí ~k~ thành ~u~ (~1 \le k \le n, 1 \le u \le 10^9~).
  • ~2\ a\ b~: In tổng các giá trị trong đoạn ~[a, b]~ (~1 \le a \le b \le n~).

Input

  • Dòng đầu tiên gồm hai số tự nhiên ~n~ và ~q~, lần lượt là số lượng phần tử và số lượng truy vấn (~1 \le n, q \le 2 \cdot 10^5~).
  • Dòng thứ hai gồm ~n~ số nguyên ~x_1, x_2, \dots, x_n~ là các giá trị của dãy số (~1 \le x_i \le 10^9~).
  • ~q~ dòng tiếp theo mỗi dòng gồm ba số nguyên thể hiện các truy vấn loại ~1~ hoặc ~2~.

Output

Với mỗi truy vấn loại ~2~ in ra kết quả tương ứng.

Sample Input 1

8 4
3 2 4 5 1 1 5 3
2 1 4
2 5 6
1 3 1
2 1 4

Sample Output 1

14
2
11

Bình luận

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


  • 0
    vominhmanh10  đã bình luận lúc 2, Tháng 5, 2026, 12:38

    bài này dùng BIT một cách đơn giản mà, chia căn có phức tạp không?

    #include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ull = unsigned long long;
#define all(a) a.begin(), a.end()
#define fi first 
#define se second
#define pii pair&lt;ll, ll>
#define IO ios::sync_with_stdio(0); cin.tie(0)
#define eb emplace_back
#define pb push_back
#define filled(a, b) memset(a, b, sizeof(a))
#define mini(a, b) (a) = (min((a), (b)))
#define maxi(a, b) (a) = (max((a), (b)))
#define fast_func inline __attribute__((always_inline))
const ll maxn = 1e6 + 5, inf = 1e18, mod = 5e6;
const ull base = 314;
int n, q;
ll bit[maxn];
fast_func void add(int i, ll x) {
    for (; i <= n; i += i & -i) bit[i] += x;
}
fast_func ll get(int i) {
    ll res = 0;
    for (; i > 0; i -= i & -i) res += bit[i];
    return res;
}
int main() {
    IO; cin >> n >> q; vector<ll> a(n + 1);
    for (int i = 1; i <= n; i++) {
        cin >> a[i];
        add(i, a[i]);
    }
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int k;
            ll x; cin >> k >> x;
            ll cur = x - a[k];
            a[k] = x;
            add(k, cur); 
        } else {
            int l, r; cin >> l >> r;
            cout << get(r) - get(l - 1) << '\n';
        }
    }
}

  • -1
    haiduong151109  đã bình luận lúc 10, Tháng 2, 2026, 8:10

    Đỗ Phạm Gia Minh 11 Tin nick trumffso1vn chê bài quá dễ @trumffso1vn


  • -5
    quangnhat123  đã bình luận lúc 5, Tháng 1, 2026, 10:08

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.


  • -15
    chunguyen2k8  đã bình luận lúc 21, Tháng 3, 2024, 9:12

    Bình luận này đã bị ẩn vì có quá nhiều phản ứng tiêu cực. Nhấn để xem.