lections

View Github Repository Open presentation in a new window

lionell

See all presentation from lionell

lections

0 0

lections

Materials from lections(presentations, etc.)

On Github lionell / lections

DATA STRUCTURES

QUICK START

Created by Ruslan Sakevych / @lionell

Segment tree

operation time build N get log(N) range update log(N) sum, min/max, gcd/lcm, ... log(N)
## API ``` int a[] = {1, 2, 3, 4, 5, 6}; build(); sum(1, 4); // 2 + 3 + 4 + 5 = 16 sum(4, 5); // 5 + 6 = 11 update(2, 10); // a[2] = 10 sum(2, 3); // 2 + 10 = 12 ```
# ALERT!!! ``` int t[4 * MAX_N]; // MEMORY LIMIT ```
## BUILD ``` void build(int v = 1, int tl = 0, int tr = n - 1) { if (tl == tr) { t[v] = a[tl]; } else { int tm = (tl + tr) / 2; build(2 * v, tl, tm); build(2 * v + 1, tm + 1, tr); t[v] = t[2 * v] + t[2 * v + 1]; } } ```
## SUM ``` int sum(int l, int r, int v = 1, int tl = 0, int tr = n - 1) { if (l > r) { return 0; } if (tl == l && tr == r) { return t[v]; } int tm = (tl + tr) / 2; return sum(l, min(r, tm), 2 * v, tl, tm) + sum(max(tm + 1, l), r, a, 2 * v + 1, tm + 1, tr); } ```
## UPDATE v1 ``` void update(int i, int val, int v = 1, int tl = 0, int tr = n - 1) { if (tl == tr) { t[v] = val; } else { int tm = (tl + tr) / 2; if (i <= tm) { update(i, val, 2 * v, tl, tm); } else { update(i, val, 2 * v + 1, tm + 1, tr); } t[v] = t[2 * v] + t[2 * v + 1]; } } ```
## TYPE OVERFLOW ``` ... int tm = tl + (tr - tl) / 2; // instead of int tm = (tl + tr) / 2; ... ```
## BITWISE OPERATIONS ``` x >> 1 // instead of x / 2 x << 1 // instead of x * 2 ```
## TAIL-CALL Recursive call of update is tail-call. So we can easily convert it to loop.

MOVING FORWARD

Now, we need some universal method for queries.

Let's define some function that can combine useful information from child nodes.

``` T t[MAX_N]; T combine(T l, T r) { ... } T make(...) { ... } ```
``` void build(...) { if (tl == tr) { // t[v] = a[tl]; t[v] = make(a[tl]); } else { int tm = tl + (tr - tl) / 2; build(2 * v, tl, tm); build(2 * v + 1, tm + 1, tr); // t[v] = t[2 * v] + t[2 * v + 1]; t[v] = combine(t[2 * v], t[2 * v + 1]); } } ```
``` void update(int i, T val, ...) { if (tl == tr) { // t[v] = val; t[v] = make(val); } else { int tm = tl + (tr - tl) / 2; if (i <= tm) { update(i, val, 2 * v, tl, tm); } else { update(i, val, 2 * v + 1, tm + 1, tr); } // t[v] = t[2 * v] + t[2 * v + 1]; t[v] = combine(t[2 * v], t[2 * v + 1]); } } ```
## ANOTHER RANGE QUERIES * min/max * min/max + **times** * gcd/lcm * zero-count & k-th zero * prefix with sum
## SEE ALSO * [Dima and array (easy, #2941 @e-olymp)](http://www.e-olymp.com/en/problems/2941) * [Range Variation Query (medium, #695 @e-olymp)](http://www.e-olymp.com/en/problems/695) * [Segment tree contest (#6532 @e-olymp)](http://www.e-olymp.com/ru/contests/6532)

GET & RANGE INCREMENT

API example ``` int a[] = {0, 0, 0, 0, 0}; inc(1, 3, 1); // a = {0, 1, 1, 1, 0} inc(0, 2, -2); // a = {-2, -1, -1, 1, 0} get(1); // a[1] == -1 ```
``` void inc(int l, int r, int x, ...) { if (l > r) { return; } if (tl == l && tr == r) { t[v] += x; } else { int tm = tl + (tr - tl) / 2; inc(l, min(r, tm), x, 2 * v, tl, tm); inc(max(tm + 1, l), x, r, 2 * v + 1, tm + 1, tr); } } ```
``` int get(int i, ...) { if (tl == tr) { return a[i]; } int tm = tl + (tr - tl) / 2; if (i <= tm) { return t[v] + get(i, 2 * v, tl, tm); } return t[v] + get(i, 2 * v + 1, tm + 1, tr); } ```

GET & RANGE ASSIGNMENT

API example ``` int a[] = {0, 0, 0, 0, 0}; let(3, 4, 1); // a = {0, 0, 0, 1, 1} let(2, 3, 7); // a = {0, 0, 7, 7, 1} get(3); // a[1] == 7 ```
``` void push(int v) { if (t[v] == -1) { return; } t[v * 2] = t[2 * v + 1] = t[v]; t[v] = -1; } ```
``` void let(int l, int r, int x, ...) { if (l > r) { return; } if (tl == l && tr == r) { t[v] = x; } else { push(v); int tm = tl + (tr - tl) / 2; let(l, min(r, tm), x, 2 * v, tl, tm); let(max(l, tm + 1), x, r, 2 * v + 1, tm + 1, tr); } } ```
``` int get(int i, ...) { if (tl == tr) { return t[v]; } push(v); int tm = tl + (tr - tl) / 2; if (i <= tm) { return get(i, 2 * v, tl, tm); } return get(i, 2 * v + 1, tm + 1, tr); } ```

SUM & RANGE ASSIGNMENT

API example ``` int a[] = {1, 2, 0, 4, 0}; build(); let(3, 4, 1); // a = {1, 2, 0, 1, 1} let(2, 3, 7); // a = {1, 2, 7, 7, 1} sum(1, 3); // 2 + 7 + 7 = 16 ```
``` pii get(int v, int tl, int tr) { return t[v].second == INF ? t[v].first : t[v].second * (tr - tl + 1); } ```
``` void push(int v) { if (t[v].second == INF) { return; } t[2 * v].second = t[2 * v + 1].second = t[v].second; t[v].second = INF; } ```
``` void let(int l, int r, int x, ...) { if (l > r) { return; } if (tl == l && tr == r) { t[v].second = x; } else { push(v); int tm = tl + (tr - tl) / 2; let(l, min(r, tm), x, 2 * v, tl, tm); let(max(l, tm + 1), r, x, 2 * v + 1, tm + 1, tr); t[v] = {get(2 * v, tl, tm) + get(2 * v + 1, tm + 1, tr), INF}; } } ```
``` int sum(int l, int r, ...) { if (l > r) { return 0; } if (tl == l && tr == r) { return get(v, tl, tr); } push(v); int tm = tl + (tr - tl) / 2; return sum(l, min(r, tm), 2 * v, tl, tm) + sum(max(l, tm + 1), r, 2 * v + 1, tm + 1, tr); } ```
## SEE ALSO * [e-maxx/segment_tree](http://e-maxx.ru/algo/segment_tree) * [Everything About Segment Trees @Codeforces](http://codeforces.com/blog/entry/15890)

Cartesian tree/Treap

operation time build N split/merge log(N) k-th element log(N) insert/remove log(N) reverse log(N) sum, min/max, ... log(N)

SIMPLE OPERATIONS

API example ``` t->insert(1); // t = {4} ... t->insert(6); // t = {1, 2, 3, 4, 5, 6} t->remove(3); // t = {1, 2, 4, 5, 6} t->split(2, l, r); // l = {1}, r = {2, 4, 5, 6} r->sum(); // 2 + 4 + 5 + 6 = 17 t = merge(l, r); // t = {1, 2, 4, 5, 6} ```
``` struct Treap { int x; int y; Treap *left; Treap *right; Treap(int x, int y, Treap *left, Treap *right); static Treap *merge(Treap *l, Treap* r); void split(int key, Treap *l, Treap *r); Treap *insert(int x); Treap *remove(int x); }; ```
``` static Treap *merge(Treap *l, Treap *r) { if (l == nullptr) { return r; } if (r == nullptr) { return l; } if (l->y > r->y) { Treap *newRight = merge(l->right, r); return new Treap(l->x, l->y, l->left, newRight); } else { Treap *newLeft = merge(l, r->left); return new Treap(r->x, r->y, newLeft, r->right); } } ```
``` void split(int key, Treap *l, Treap *r) { Treap *newTree = nullptr; if (x <= key) { if (right == nullptr) r = nullptr; else right->split(key, newTree, r); l = new Treap(x, y, left, newTree); } else { if (left == nullptr) l = nullptr; else left->split(key, l, newTree); r = new Treap(x, y, newTree, right); } } ```
``` Treap *insert(int x) { Treap *l, *r; split(x, l, r); Treap *m = new Treap(x, rand()); return merge(merge(l, m), r); } ```
``` Treap *remove(int x) { Treap *l, *m, *r, *t; split(x, m, r); m->split(x - 1, l, t); return merge(l, r); } ```

Questions?