Bài toán truy vấn tổng

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Tác giả:

jumptozero

Dạng bài

Điểm: 400 Thời gian: 1.0s Bộ nhớ: 256M Input: bàn phím Output: màn hình

Cho một mảng gồm \(N\) phần tử \(a[1],a[2],...,a[N]\) và có \(T\) truy vấn có dạng như sau:

\(1\text{ }l\text{ }r\): In ra tổng tất cả các phần tử thuộc đoạn \([l,r]\)
\(2\text{ }x\text{ }y\): Thay giá trị tại vị trí thứ \(x\) thành \(y\) (tức là gán \(a[x]=y\))

Input

Dòng thứ nhất chứa hai số nguyên \(N,T\)
Dòng thứ hai chứa \(N\) số nguyên \(a[1],a[2],...,a[N]\) \((1\leq a_i\leq 10^5)\)
\(T\) dòng tiếp theo chứa \(T\) truy vấn: \(1 \text{ }l\text{ }r\) \((1\leq l\leq r\leq n)\) hoặc \(2\text{ }x\text{ }y\) \((1\leq x\leq N, 1\leq y\leq 10^4)\)

Output

Ứng với mỗi truy vấn \(1\text{ }l\text{ }r\) in ra tổng cần tìm

Constraints

\(1\le N\le 10^4\)
\(1\le T\le 10^5\)

Example

Test 1

Input

Output

5
6

Bình luận

tplong • 8:17 a.m. 12 Tháng 4, 2024 •

Hint fenwick đc k ạ

0
Phản hồi Chia sẻ

void build(int node, int start, int end) {
    if (start == end) {
        seg[node] = a[start];
    } else {
        int mid = (start + end) / 2;
        build(2 * node, start, mid);
        build(2 * node + 1, mid + 1, end);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }
}

int query(int node, int start, int end, int L, int R) {
    if (R < start || end < L) return 0;  
    if (L <= start && end <= R) return seg[node];  
    int mid = (start + end) / 2;
    return query(2 * node, start, mid, L, R) + query(2 * node + 1, mid + 1, end, L, R);
}

void update(int node, int start, int end, int index, int value) {
    if (start == end) {
        a[index] = value;
        seg[node] = value;
    } else {
        int mid = (start + end) / 2;
        if (index <= mid)
            update(2 * node, start, mid, index, value);
        else
            update(2 * node + 1, mid + 1, end, index, value);
        seg[node] = seg[2 * node] + seg[2 * node + 1];
    }
}

Phản hồi

2 bình luận nữa