segmenttree.cpp

Đã 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));

    }

}