Đã có bài viết về lazy update cho segment tree. Các bạn có thể mở hai trang con ở bên dưới.
Bài toán
Ban đầu, dãy số của chúng ta có n phần tử bằng 0.
Có m truy vấn:
U p q : gán phần tử a[p] thành q
Q p q : in ra phần tử lớn nhất trong khoảng từ p đến q
Độ phức tạp
O (m log n)
#include <stdio.h>
int T[10230997];
int n, m;
int max(int a, int b){ return a>b?a:b; }
int query(int node, int ll, int rr, int u, int v){
if (v<ll or rr<u or ll>rr) { return -1000111000; }
if (u<=ll and ll<=rr and rr<=v) return T[node];
return max(
query(node*2, ll, (ll+rr)/2, u, v),
query(node*2+1, (ll+rr)/2+1, rr, u, v)
);
}
void update(int node, int ll, int rr, int i, int v){
if (i<ll or i>rr or ll>rr) return;
if (ll!=rr){
update(node*2, ll, (ll+rr)/2, i, v);
update(node*2+1, (ll+rr)/2+1, rr, i, v);
T[node] = max(T[node*2], T[node*2+1]);
}
else T[node] = v;
}
main(){
int p, q; char c;
init();
scanf("%d%d", &n, &m);
while (m--){
scanf(" %c%d%d", &c, &p, &q);
if (c=='u' or c=='U') update(1, 1, n, p, q);
if (c=='q' or c=='Q') printf("%d\n", query(1, 1, n, p, q));
}
}