segtree.c

#include <stdbool.h>
#define N 1<<17
struct segtree {
    int n, h;
    struct node t[2 * N];
    struct node_update d[N];
    struct node (*merge)(struct node*, struct node*);
    struct node_update (*merge_upd)(struct node_update*, struct node_update*);
    struct node (*apply_upd)(struct node*, struct node_update*);
    bool (*upd_done)(struct node_update*);
    void (*upd_clear)(struct node_update*);
};
void segtree_init(struct segtree* tr) {
    for(int i = tr->n - 1; i > 0; i--) tr->t[i] = tr->merge(&tr->t[i << 1], &tr->t[i << 1 | 1]);
    for(int i = 0; i < N; i++) tr->upd_clear(&tr->d[i]);
}
void segtree_apply(struct segtree* tr, int p, struct node_update* upd) {
    tr->t[p] = tr->apply_upd(&tr->t[p], upd);
    if(p < tr->n) tr->d[p] = tr->merge_upd(&tr->d[p], upd);
}
void segtree_build(struct segtree* tr, int p) {
    while(p > 1) {
        p >>= 1;
        tr->t[p] = tr->merge(&tr->t[p << 1], &tr->t[p << 1 | 1]);
        tr->t[p] = tr->apply_upd(&tr->t[p], &tr->d[p]);
    }
}
void segtree_push(struct segtree* tr, int p) {
    for(int s = tr->h; s > 0; s--) {
        int i = p >> s;
        if(!tr->upd_done(&tr->d[i])) {
            segtree_apply(tr, i << 1, &tr->d[i]);
            segtree_apply(tr, i << 1 | 1, &tr->d[i]);
            tr->upd_clear(&tr->d[i]);
        }
    }
}
void segtree_modify(struct segtree* tr, int l, int r, struct node_update* upd) {
    l += tr->n, r += tr->n;
    segtree_push(tr, l);
    segtree_push(tr, r - 1);
    int l0 = l, r0 = r;
    for(; l < r; l >>= 1, r >>= 1) {
        if(l & 1) segtree_apply(tr, l++, upd);
        if(r & 1) segtree_apply(tr, --r, upd);
    }
    segtree_build(tr, l0);
    segtree_build(tr, r0 - 1);
}
struct node segtree_query(struct segtree* tr, int l, int r, struct node id) {
    l += tr->n, r += tr->n;
    segtree_push(tr, l);
    segtree_push(tr, r - 1);
    struct node resl = id, resr = id;
    for(; l < r; l >>= 1, r >>= 1) {
        if(l & 1) resl = tr->merge(&resl, &tr->t[l++]);
        if(r & 1) resr = tr->merge(&tr->t[--r], &resr);
    }
    return tr->merge(&resl, &resr);
}