Bài toán
Hỗ trợ các thao tác tăng cả một đoạn lên x đơn vị và tìm max của một đoạn. Sử dụng cấp phát động.
Độ phức tạp
mỗi truy vấn : O(logn)
bộ nhớ: min(2*n, mlogn)
(n là số phần tử cần quản ly, m là số truy vấn)
Code này của Nguyễn Tiến Trung Kiên
#include <stdio.h>
#include <iostream>
#include <algorithm>
using namespace std;
struct node {
int ll, rr, Max, Lazy;
node *Left, *Right;
node(int _ll, int _rr, int _Max){ ll=_ll, rr=_rr; Max=_Max; }
void diffuse(){
if (ll!=rr){
if (!Left) Left = new node(ll, (ll+rr)/2, Max);
if (!Right) Right = new node((ll+rr)/2+1, rr, Max);
}
if (Lazy){
Max+=Lazy;
if (Left) Left->Lazy += Lazy;
if (Right) Right->Lazy += Lazy;
Lazy=0;
}
}
void update(int L, int R, int X){
diffuse();
if (L>rr || R<ll) return;
if (L<=ll && rr<=R) { Lazy+=X; diffuse(); }
else {
Left->update(L, R, X);
Right->update(L, R, X);
Max = max(Left->Max, Right->Max);
}
}
int max_range(int L, int R){
diffuse();
if (L>rr || R<ll) return -0x3c3c3c3c;
if (L<=ll && rr<=R) return Max;
else return max(Left->max_range(L, R), Right->max_range(L, R));
}
};
int n, m;
node* root;
main(){
ios :: sync_with_stdio(false);
cin >> n >> m;
root=new node(1, n, 0);
while (m--){
int x, y, z, ch;
cin >> ch >> x >> y;
if (ch==1) cout << root->max_range(x, y) << endl;
else { cin >> z; root->update(x, y, z); }
}
}
Nhận xét
Segment tree sử dụng cấp phát động có thể dùng để giải quyết với bài có n rất lớn (n<=10^9).
Code này đã được dùng để nộp cho một bài trên SPOJ.
Tham khảo