Created
January 30, 2018 19:08
-
-
Save BenjaminBLi/f882ccbf915d17995d55c4768a5c76cd to your computer and use it in GitHub Desktop.
Segment tree code (incomplete)
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
| #include <bits/stdc++.h> | |
| #define fori(i, st, en) for(int i = st; i < (int) (en); i++) | |
| #define rfori(i, st, en) for(int i = st; i >= (int) (en); i--) | |
| #define f first | |
| #define s second | |
| #define pb push_back | |
| #define left(i) (i<<1) | |
| #define right(i) (i<<1|1) | |
| #define mid(l, r) ((l+r)>>1) | |
| using namespace std; | |
| typedef long long ll; | |
| typedef vector<int> vi; | |
| typedef pair<int, int> ii; | |
| typedef long long ll; | |
| typedef vector<ii> vii; | |
| typedef double lf; | |
| struct node{ | |
| int l, r; | |
| int val; | |
| node(){val = 0;} | |
| void apply(int a); | |
| void calc(); | |
| void upd(int idx, int val); | |
| void build(int l, int r); | |
| node *left, *right; | |
| }root; | |
| void node::build(int cl, int cr){ | |
| l = cl, r = cr; | |
| if(l == r){ | |
| return; | |
| } | |
| left = new node(); | |
| right = new node(); | |
| left->build(cl, mid(cl, cr)), right->build(mid(cl, cr)+1, cr); | |
| } | |
| void node::apply(int c){ | |
| val = c; | |
| } | |
| void node::calc(){ | |
| val = __gcd(left->val, right->val); | |
| } | |
| void node::upd(int pt, int p){ | |
| if(pt <= l && r <= pt){ | |
| apply(p); | |
| return; | |
| }else if(r < pt || pt < l) return; | |
| left->upd(pt, p), right->upd(pt, p); | |
| calc(); | |
| } |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment