Hướng giải của Cộng Đoạn Tính Tổng Đoạn

Nhớ rằng hướng dẫn giải này chỉ nên sử dụng khi bế tắc, và tuyệt đối không nên sao chép mã nguồn kèm theo. Hãy tôn trọng tác giả bài tập và người viết hướng dẫn giải.
Nộp mã nguồn lời giải chính thức trước khi giải bài tập đó có thể khiến bạn bị ban.

Tác giả: kienadmin

Hướng dẫn giải

Bài toán yêu cầu thực hiện đồng thời cập nhật đoạn và truy vấn tổng đoạn. Ta phân tích công thức tính tổng tiền tố \(S[i] = \sum_{x=1}^{i} A[x]\) dưới mảng hiệu \(D\): \[S[i] = \sum_{x=1}^{i} \sum_{y=1}^{x} D[y] = \sum_{y=1}^{i} (i - y + 1) \cdot D[y] = (i + 1) \cdot \sum_{y=1}^{i} D[y] - \sum_{y=1}^{i} y \cdot D[y]\] Do đó, ta cần duy trì 2 cây Fenwick Tree:

  1. bit1 quản lý các giá trị \(D[y]\).
  2. bit2 quản lý các giá trị \(y \cdot D[y]\).

Khi cập nhật đoạn \([l, r]\) thêm \(val\):

  • Trên bit1: cộng \(val\) tại \(l\), trừ \(val\) tại \(r+1\).
  • Trên bit2: cộng \(val \cdot (l - 1)\) tại \(l\), trừ \(val \cdot r\) tại \(r+1\).

Độ phức tạp thời gian: \(O(\log N)\) mỗi thao tác.

Mã nguồn C++ mẫu

#include <bits/stdc++.h>
using namespace std;

int n, q;
vector<long long> bit1, bit2;

void update(vector<long long>& bit, int i, long long val) {
    for (; i <= n; i += i & -i) bit[i] += val;
}

long long query(const vector<long long>& bit, int i) {
    long long s = 0;
    for (; i > 0; i -= i & -i) s += bit[i];
    return s;
}

void range_update(int l, int r, long long val) {
    update(bit1, l, val);
    update(bit1, r + 1, -val);
    update(bit2, l, val * (l - 1));
    update(bit2, r + 1, -val * r);
}

long long prefix_query(int i) {
    return query(bit1, i) * i - query(bit2, i);
}

int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    if (!(cin >> n >> q)) return 0;
    bit1.assign(n + 2, 0);
    bit2.assign(n + 2, 0);
    while (q--) {
        int t; cin >> t;
        if (t == 1) {
            int l, r; long long val; cin >> l >> r >> val;
            range_update(l, r, val);
        } else {
            int l, r; cin >> l >> r;
            cout << prefix_query(r) - prefix_query(l - 1) << "\n";
        }
    }
}

Nhận xét

Không có ý kiến tại thời điểm này.