## Xét bài toán sau:
Cho mảng $a$ gồm $n$ phần tử, ban đầu đều có giá trị là $0$. Cho $q$ truy vấn có dạng $(l,r,w)$, tăng giá trị các phần từ $l$ đến $r$ thêm $w$ đơn vị.
Tìm giá trị của mỗi phần tử sau $q$ truy vấn.
### Ý tưởng:
Nếu ta cập nhật từng phần tử thì sẽ mất độ phức tạp $O(qn)$ là quá chậm.
Thay vào đó, ta sử dụng kỹ thuật **Mảng hiệu**:
- Tạo 1 mảng $D$ gồm $n$ phần tử đều là $0$.
- Với mỗi truy vấn, ta tăng $D[l]$ thêm $w$ và giảm $D[r+1]$ đi $w$ đơn vị.
- Sau khi xử lí xong $q$ truy vấn, ta khôi phục mảng kết quả $a$ bằng cách cộng dồn $a[i] = D[i] + a[i-1]$ với $i$ từ $1 \rightarrow n$. Khi này, mảng $a$ chính là mảng kết quả cần tìm.
Độ phức tạp: $O(q + n)$.
---
## Áp dụng ý tưởng trên vào bài toán này:
Gọi $LCA(u,v)$ là $a$ và mảng $par$ với $par[i]$ là cha của đỉnh $i$.
Dễ thấy ta cần cập nhật các đỉnh từ $u \rightarrow a$ và $v \rightarrow a$.
Tạo một mảng $W$ gồm $n$ phần tử đều là $0$ với $W[i]$ là giá trị trên đỉnh $i$ sau các truy vấn.
Với mỗi truy vấn, ta:
- Tăng $W[u]$ và $W[v]$ thêm $w$ đơn vị.
- Giảm $W[a]$ và $W[par[a]]$ đi $w$ đơn vị.
Sau khi thực hiện hết $q$ truy vấn, gọi $h[i]$ là độ sâu của đỉnh $i$ tính từ gốc. Ta cần duyệt lại các đỉnh theo thứ tự $h[i]$ giảm dần (hay theo thứ tự từ lá đến gốc).
Do thứ tự duyệt trên nên ta cập nhật $W[par[i]] = W[par[i]] + W[i]$.
Sau cùng, ta có mảng $W$ là kết quả của bài toán.
*Lưu ý, khi duyệt đến đỉnh $a$, $W[a]$ sẽ bị cập nhật 2 lần (từ 2 đỉnh con kề $a$ nhất trên đường đi đơn từ $u \rightarrow v$). Đó là lý do ta cần phải giảm $W[a]$ đi $w$ đơn vị ở mỗi truy vấn.*
### Độ phức tạp:
- Ta có thể dùng **Binary Lifting** để tìm $LCA(u,v)$ trong $O(\log n)$.
- **Độ phức tạp tiền xử lí: $O(n \log n)$**.
- **Độ phức tạp mỗi truy vấn: $O(\log n)$**.
- **Độ phức tạp khôi phục: $O(n)$**.
- **Có $q$ truy vấn, vì thế tổng độ phức tạp là: $O(n \log n + q \log n + n) = O((n+q) \log n)$**.
---
## Code mẫu:
```cpp
#include <bits/stdc++.h>
#define pb push_back
#define fi first
#define se second
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
template<typename A,typename B> bool minimize(A& a,const B& b) {return a > b ? a = b, 1 : 0;}
template<typename A,typename B> bool maximize(A& a,const B& b) {return a < b ? a = b, 1 : 0;}
using namespace std;
const int maxn = 1e5+5;
int n,q;
vector<int> edge[maxn],hi[maxn];
int h[maxn];
ll W[maxn];
int up[maxn][16];
void dfs(int u){
for(auto v:edge[u]){
if(v == up[u][0]) continue;
h[v] = h[u]+1;
up[v][0] = u;
for(int j=1;j<16;j++) up[v][j] = up[up[v][j-1]][j-1];
dfs(v);
}
}
int lca(int u,int v){
if(h[u] != h[v]){
if(h[u] < h[v]) swap(u,v);
int k = h[u]-h[v];
for(int j=0;j<16;j++){
if((k>>j)&1) u = up[u][j];
}
}
if(u == v) return u;
int k = __lg(h[u]);
for(int j=k;j>=0;j--){
if(up[u][j] != up[v][j]){
u = up[u][j];
v = up[v][j];
}
}
return up[u][0];
}
int main()
{
ios_base::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
cin>>n>>q;
for(int i=1;i<n;i++){
int u,v;cin>>u>>v;
edge[u].pb(v);
edge[v].pb(u);
}
dfs(1);
while(q--){
int u,v,w;
cin>>u>>v>>w;
int ca = lca(u,v);
W[u] += w;
W[v] += w;
W[ca] -= w;
W[up[ca][0]] -= w;
}
int maxh = 0;
for(int i=1;i<=n;i++) {
hi[h[i]].pb(i);
maximize(maxh,h[i]);
}
for(int i=maxh;i>=0;i--){
for(auto v:hi[i]){
W[up[v][0]] += W[v];
}
}
for(int i=1;i<=n;i++) cout<<W[i]<<' ';
return 0;
}
```
# Vấn đề
Cách duyệt trâu: duyệt từ $u \to v$, cập nhật trực tiếp từng đỉnh. Điều này tốn $O(n)$ cho mỗi truy vấn,
tổng $O(qn)$.
Quá lớn với $q, n \leq 10^5$.
Do đó ta tối ưu bằng Binary Lifting + LCA.
Đầu tiên ta tạo bảng `up` bằng binary lifting để tìm $\text{LCA}(u, v)$ trong $O(\log n)$.
## Thay vì duyệt trực tiếp, ta:
- Cập nhật từ $u \to \text{LCA}(u, v)$
- Cập nhật từ $v \to \text{LCA}(u, v)$
- Cộng $w$ thêm 1 lần cho đỉnh chung
## Độ phức tạp
- Duyệt DFS + build `up[][]`: $O(n \log n)$
- Mỗi truy vấn: $O(\log n)$
- Tổng: $O((n + q) \log n)$
---
## Code minh hoạ
```cpp
#include <bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e5 + 5;
const int l = 17;
vector<int> gr[maxn];
bool vis[maxn];
int up[maxn][l];
vector<ll> answ(maxn, 0);
int dep[maxn];
// DFS
void dfs(int u, int p) {
vis[u] = true;
up[u][0] = p;
for (int i = 1; i < l; i++) {
up[u][i] = up[up[u][i - 1]][i - 1];
}
for (int v : gr[u]) {
if (!vis[v]) {
dep[v] = dep[u] + 1;
dfs(v, u);
}
}
}
// Find LCA
int find_lca(int u, int v) {
if (dep[u] < dep[v]) swap(u, v);
for (int i = l - 1; i >= 0; i--) {
if (dep[u] - (1 << i) >= dep[v]) {
u = up[u][i];
}
}
if (u == v) return u;
for (int i = l - 1; i >= 0; i--) {
if (up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
// Update
void update(int u, int res, ll w) {
while (u != res) {
answ[u] += w;
u = up[u][0];
}
}
// Main
int main() {
int n, q;
cin >> n >> q;
for (int i = 0; i < n - 1; i++) {
int u, v;
cin >> u >> v;
gr[u].push_back(v);
gr[v].push_back(u);
}
memset(vis, false, sizeof(vis));
memset(dep, 0, sizeof(dep));
dfs(1, 0);
while (q--) {
int u, v;
ll w;
cin >> u >> v >> w;
int res = find_lca(u, v);
update(u, res, w);
update(v, res, w);
answ[res] += w;
}
for (int i = 1; i <= n; i++) cout << answ[i] << " ";
}
GTai4210
Created at
3 likes
kiennosad
Created at
0 likes