라이브러리/자료구조4 Segment tree struct Segt { using T = int; static constexpr T def = 1= 1; ) { seg[i] = segfun(seg[i 2021. 8. 12. BIT struct Bit { ll cap; vector arr, tree; Bit(int size) { cap = size + 1; arr.resize(cap, 0); tree.resize(cap, 0); } void update(int i, ll x) { ll diff = x; arr[i] += x; while (i 0) { ret += tree[i]; i -= i & -i; } return ret; } }; 2021. 3. 22. DSU int dsfind(int tar) { if (tar == root[tar]) return tar; return root[tar] = dsfind(root[tar]); } void dsmerge(int a, int b) { a = dsfind(a), b = dsfind(b); if (a != b) root[a] = b; } 2021. 3. 22. Tree #include using namespace std; typedef long long ll; const int MAX = 100001; int parent[MAX]; struct Tree { int root, size; vector child[MAX], edge[MAX]; Tree() { root = -1; size = 0; } Tree(int n) { root = -1; size = n; } void addEdge(int u, int v) { edge[u].push_back(v); edge[v].push_back(u); } void build(int id) { if (root == -1) root = id; for (int next : edge[id]) { if (!parent[next]) { pare.. 2020. 8. 6. 이전 1 다음
