Last active
February 12, 2023 04:06
-
-
Save jacky860226/3d32718ecadf770604031ce46d554506 to your computer and use it in GitHub Desktop.
Sparse Segment Tree (for IOI 2013 Game)
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| template <class ValueTy> struct Tree { | |
| int L, R; | |
| Tree *lc, *rc; | |
| ValueTy Val; | |
| Tree() = default; | |
| Tree(int L, int R) : L(L), R(R), lc(nullptr), rc(nullptr), Val() {} | |
| void pull() { | |
| Val = 0; | |
| if (lc) | |
| Val += lc->Val; | |
| if (rc) | |
| Val += rc->Val; | |
| } | |
| static void ensure(Tree *&T, int p, int L, int R) { | |
| if (!T) { | |
| T = new Tree(p, p + 1); | |
| return; | |
| } | |
| if (T->L <= p && p < T->R) { | |
| return; | |
| } | |
| auto mid = [&L, &R]() { return (L + R) / 2; }; | |
| while ((p < mid()) == (T->L < mid())) | |
| ((p < mid()) ? R : L) = mid(); | |
| Tree *T_new = new Tree(L, R); | |
| ((T->L < mid()) ? T_new->lc : T_new->rc) = T; | |
| T = T_new; | |
| T->pull(); | |
| } | |
| void update(int p, const ValueTy &Val_new) { | |
| if (L + 1 == R) { | |
| Val = Val_new; | |
| } else { | |
| int mid = (L + R) / 2; | |
| if (p < mid) { | |
| ensure(lc, p, L, mid); | |
| lc->update(p, Val_new); | |
| } else { | |
| ensure(rc, p, mid, R); | |
| rc->update(p, Val_new); | |
| } | |
| pull(); | |
| } | |
| } | |
| ValueTy query(int qL, int qR) { | |
| if (qR <= L || R <= qL) | |
| return ValueTy(); | |
| if (qL <= L && R <= qR) | |
| return Val; | |
| auto ans = ValueTy(); | |
| if (lc) | |
| ans = ans + lc->query(qL, qR); | |
| if (rc) | |
| ans = ans + rc->query(qL, qR); | |
| return ans; | |
| } | |
| const ValueTy &operator=(const ValueTy &Other) { | |
| L = Other.L; | |
| R = Other.R; | |
| Val = Other.Val; | |
| if (Other.lc) { | |
| lc = new Tree(); | |
| *lc = *Other.lc; | |
| } | |
| if (Other.rc) { | |
| rc = new Tree(); | |
| *rc = *Other.rc; | |
| } | |
| return *this; | |
| } | |
| }; |
This file contains hidden or bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| template <class ValueTy> struct Tree { | |
| int L, R; | |
| Tree *lc, *rc; | |
| ValueTy Val; | |
| Tree() = default; | |
| Tree(int L, int R) : L(L), R(R), lc(nullptr), rc(nullptr), Val() {} | |
| void pull() { | |
| Val = 0; | |
| if (lc) | |
| Val += lc->Val; | |
| if (rc) | |
| Val += rc->Val; | |
| } | |
| static void ensure(Tree *&T, int p, int L, int R) { | |
| if (!T) { | |
| T = new Tree(p, p); | |
| return; | |
| } | |
| if (T->L <= p && p <= T->R) { | |
| return; | |
| } | |
| bool is_update = false; | |
| do { | |
| is_update = false; | |
| int mid = (L + R) / 2; | |
| if (p <= mid && T->R <= mid) { | |
| R = mid; | |
| is_update = true; | |
| } | |
| if (p > mid && T->L > mid) { | |
| L = mid + 1; | |
| is_update = true; | |
| } | |
| } while (is_update); | |
| Tree *T_new = new Tree(L, R); | |
| ((T->L <= (L + R) / 2) ? T_new->lc : T_new->rc) = T; | |
| T = T_new; | |
| T->pull(); | |
| } | |
| void update(int p, const ValueTy &Val_new) { | |
| if (L == R) { | |
| Val = Val_new; | |
| } else { | |
| int mid = (L + R) / 2; | |
| if (p <= mid) { | |
| ensure(lc, p, L, mid); | |
| lc->update(p, Val_new); | |
| } else { | |
| ensure(rc, p, mid + 1, R); | |
| rc->update(p, Val_new); | |
| } | |
| pull(); | |
| } | |
| } | |
| ValueTy query(int qL, int qR) { | |
| if (qR < L || R < qL) | |
| return ValueTy(); | |
| if (qL <= L && R <= qR) | |
| return Val; | |
| auto ans = ValueTy(); | |
| if (lc) | |
| ans = ans + lc->query(qL, qR); | |
| if (rc) | |
| ans = ans + rc->query(qL, qR); | |
| return ans; | |
| } | |
| const ValueTy &operator=(const ValueTy &Other) { | |
| L = Other.L; | |
| R = Other.R; | |
| Val = Other.Val; | |
| if (Other.lc) { | |
| lc = new Tree(); | |
| *lc = *Other.lc; | |
| } | |
| if (Other.rc) { | |
| rc = new Tree(); | |
| *rc = *Other.rc; | |
| } | |
| return *this; | |
| } | |
| }; |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment