Hướng giải của Kho lương thực

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

Nhận xét

Bài toán yêu cầu vừa cập nhật giá trị đỉnh vừa truy vấn tổng subtree. Nếu duyệt DFS mỗi lần thì độ phức tạp \(O(NQ)\), không khả thi.

Ý tưởng giải

Sử dụng Euler Tour Type 1 (mỗi đỉnh xuất hiện 1 lần) kết hợp với Fenwick Tree (BIT):

  1. Euler Tour: DFS từ gốc, ghi \(tin[u]\) và \(tout[u]\). Subtree của \(u\) ứng với đoạn \([tin[u], tout[u]]\) trong mảng Euler.
  2. BIT: Lưu giá trị đỉnh \(u\) tại vị trí \(tin[u]\). BIT hỗ trợ cập nhật điểm và truy vấn tổng đoạn trong \(O(\log N)\).
  3. Cập nhật: Tính delta = new_val - old_val, cập nhật BIT tại vị trí \(tin[u]\).
  4. Truy vấn: Tổng subtree = query(tout[u]) - query(tin[u] - 1).

Độ phức tạp

  • Tiền xử lý DFS: \(O(N)\), build BIT: \(O(N \log N)\)
  • Mỗi truy vấn: \(O(\log N)\)
  • Tổng: \(O((N + Q) \log N)\)

Code mẫu

// Giải thuật ett cho bài toán ett-subtree-sum\n#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MAXN = 200005;
vector<int> adj[MAXN];
int tin[MAXN], tout[MAXN];
ll val[MAXN];
ll bit[MAXN];
int timer_dfs = 0;
int n, q;

void bit_update(int i, ll delta) {
    for (; i <= n; i += i & (-i))
        bit[i] += delta;
}

ll bit_query(int i) {
    ll sum = 0;
    for (; i > 0; i -= i & (-i))
        sum += bit[i];
    return sum;
}

ll range_query(int l, int r) {
    return bit_query(r) - bit_query(l - 1);
}

void dfs(int u, int parent) {
    tin[u] = ++timer_dfs;
    for (int v : adj[u]) {
        if (v != parent) {
            dfs(v, u);
        }
    }
    tout[u] = timer_dfs;
}

int main() {
    // Doc du lieu dau vao
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> q;
    for (int i = 1; i <= n; i++) cin >> val[i];

    for (int i = 0; i < n - 1; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    dfs(1, 0);

    // Khoi tao BIT voi gia tri ban dau
    for (int i = 1; i <= n; i++) {
        bit_update(tin[i], val[i]);
    }

    while (q--) {
        int type;
        cin >> type;
        if (type == 1) {
            int u;
            ll new_val;
            cin >> u >> new_val;
            ll delta = new_val - val[u];
            val[u] = new_val;
            bit_update(tin[u], delta);
        } else {
            int u;
            cin >> u;
            cout << range_query(tin[u], tout[u]) << "\n";
        }
    }
    return 0;
}

Nhận xét

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