Skip to content

Instantly share code, notes, and snippets.

@f2lk6wf90d f2lk6wf90d/segtree.c Secret
Last active May 16, 2017

Embed
What would you like to do?
#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);
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.