Untitled
unknown
c_cpp
9 months ago
37 kB
7
Indexable
#ifndef CHEATSHEET_H
#define CHEATSHEET_H
#include <algorithm>
#include <iostream>
#include <vector>
#include <queue>
#include <stack>
#include <tuple>
#include <math.h>
#include <functional>
using namespace std;
//=====================================================================================
// 1. bfs, dfs - pe un graf orientat sau neorientat (retinere generica)
// usage example:
// graf g(5, false);
// g.adaugaMuchie(0, 1);
// g.adaugaMuchie(1, 2);
// vector<int> rez_bfs = g.bfs(0);
// vector<int> rez_dfs = g.dfs(0);
//=====================================================================================
class Graf {
public:
int n;
bool orientat;
vector<vector<int>> adj;
Graf(int n, bool orientat = false) : n(n), orientat(orientat) {
adj.resize(n);
}
void adaugaMuchie(int u, int v) {
adj[u].push_back(v);
if(!orientat) {
adj[v].push_back(u);
}
}
// bfs
vector<int> bfs(int start) {
vector<int> viz(n, 0), rez;
queue<int> q;
viz[start] = 1;
q.push(start);
while(!q.empty()) {
int node = q.front();
q.pop();
rez.push_back(node);
for(auto &vecin : adj[node]) {
if(!viz[vecin]) {
viz[vecin] = 1;
q.push(vecin);
}
}
}
return rez;
}
// dfs (recursiv)
void dfsUtil(int node, vector<int> &viz, vector<int> &rez) {
viz[node] = 1;
rez.push_back(node);
for(auto &vecin : adj[node]) {
if(!viz[vecin]) {
dfsUtil(vecin, viz, rez);
}
}
}
vector<int> dfs(int start) {
vector<int> viz(n, 0), rez;
dfsUtil(start, viz, rez);
return rez;
}
};
//=====================================================================================
// 2. noduri critice (articulation points) si muchii critice (bridges)
// usage example (stapane, daca vrei sa afli ce noduri si muchii iti pot da dureri de cap):
// graphcritic gc(5);
// gc.adaugaMuchie(0,1);
// gc.adaugaMuchie(1,2);
// gc.findArticulationPointsAndBridges();
// vector<bool> ap = gc.articulation;
// vector<pair<int,int>> br = gc.bridges;
//=====================================================================================
class GraphCritic {
public:
int n;
vector<vector<int>> adj;
vector<int> disc, low, parent;
vector<bool> articulation;
int timp;
vector<pair<int,int>> bridges;
GraphCritic(int n) : n(n) {
adj.resize(n);
disc.resize(n, -1);
low.resize(n, -1);
parent.resize(n, -1);
articulation.resize(n, false);
timp = 0;
}
void adaugaMuchie(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
void dfsAP(int u) {
disc[u] = low[u] = timp++;
int copii = 0;
for(int v : adj[u]) {
if(disc[v] == -1) {
parent[v] = u;
copii++;
dfsAP(v);
low[u] = min(low[u], low[v]);
if(parent[u] == -1 && copii > 1) {
articulation[u] = true;
}
if(parent[u] != -1 && low[v] >= disc[u]) {
articulation[u] = true;
}
if(low[v] > disc[u]) {
bridges.push_back({u, v});
}
} else if(v != parent[u]) {
low[u] = min(low[u], disc[v]);
}
}
}
void findArticulationPointsAndBridges() {
for(int i = 0; i < n; i++) {
if(disc[i] == -1) {
dfsAP(i);
}
}
}
};
//=====================================================================================
// 3. tarjan pentru strongly connected components (graf orientat)
// usage example (ai un graf orientat si vrei scc?):
// tarjanscc t(5);
// t.adaugaMuchie(0,1);
// t.adaugaMuchie(1,2);
// t.buildSCCs();
// vector<vector<int>> componente = t.sccs;
//=====================================================================================
class TarjanSCC {
public:
int n;
vector<vector<int>> adj;
vector<int> disc, low, stiva;
vector<bool> inStack;
int timp;
vector<vector<int>> sccs;
TarjanSCC(int n) : n(n) {
adj.resize(n);
disc.resize(n, -1);
low.resize(n, -1);
inStack.resize(n, false);
timp = 0;
}
void adaugaMuchie(int u, int v) {
adj[u].push_back(v);
}
void tarjanDFS(int u) {
disc[u] = low[u] = timp++;
stiva.push_back(u);
inStack[u] = true;
for(auto &v : adj[u]) {
if(disc[v] == -1) {
tarjanDFS(v);
low[u] = min(low[u], low[v]);
} else if(inStack[v]) {
low[u] = min(low[u], disc[v]);
}
}
if(low[u] == disc[u]) {
vector<int> comp;
while(true) {
int node = stiva.back();
stiva.pop_back();
inStack[node] = false;
comp.push_back(node);
if(node == u) break;
}
sccs.push_back(comp);
}
}
void buildSCCs() {
for(int i = 0; i < n; i++) {
if(disc[i] == -1) {
tarjanDFS(i);
}
}
}
};
//=====================================================================================
// 4. verificare bipartit (graf neorientat) - bfs/dfs
// usage example (vrei sa vezi daca graful e bipartit?):
// vector<vector<int>> adj(4);
// adj[0] = {1};
// adj[1] = {0,2};
// bool e_ok = bipartit_check(adj);
//=====================================================================================
bool bipartit_check(const vector<vector<int>> &adj) {
int n = (int)adj.size();
vector<int> color(n, -1);
for(int start = 0; start < n; start++) {
if(color[start] == -1) {
queue<int> q;
color[start] = 0;
q.push(start);
while(!q.empty()) {
int u = q.front();
q.pop();
for(auto &v : adj[u]) {
if(color[v] == -1) {
color[v] = 1 - color[u];
q.push(v);
} else if(color[v] == color[u]) {
return false;
}
}
}
}
}
return true;
}
//=====================================================================================
// 5. euler path/circuit (hierholzer) - pentru graf neorientat eulerian
// usage example (bai stapane, daca graful tau are toate gradele pare, poti sa faci asa):
// vector<vector<int>> adj(3);
// adj[0] = {1,2};
// adj[1] = {0,2};
// adj[2] = {0,1};
// vector<int> circuit = eulerian_circuit(adj);
//=====================================================================================
vector<int> eulerian_circuit(vector<vector<int>> &adj) {
vector<int> circuit;
stack<int> st;
st.push(0);
while(!st.empty()) {
int u = st.top();
if(!adj[u].empty()) {
int v = adj[u].back();
adj[u].pop_back();
st.push(v);
} else {
circuit.push_back(u);
st.pop();
}
}
return circuit;
}
//=====================================================================================
// 6. edmond-karp (max flow) - o(v*e^2)
// usage example (cand vrei flux maxim, bossule):
// vector<vector<int>> capacity = {{0,10,0},{0,0,5},{0,0,0}};
// int mf = edmond_karp(capacity, 0, 2);
//=====================================================================================
int edmond_karp(vector<vector<int>> capacity, int source, int sink) {
int n = capacity.size();
vector<vector<int>> flow(n, vector<int>(n, 0));
int max_flow = 0;
while(true) {
vector<int> parent(n, -1);
parent[source] = source;
queue<int> q;
q.push(source);
while(!q.empty() && parent[sink] == -1) {
int u = q.front();
q.pop();
for(int v = 0; v < n; v++) {
if(capacity[u][v] - flow[u][v] > 0 && parent[v] == -1) {
parent[v] = u;
q.push(v);
}
}
}
if(parent[sink] == -1) break;
int augment = INT_MAX;
int v = sink;
while(v != source) {
int u = parent[v];
augment = min(augment, capacity[u][v] - flow[u][v]);
v = u;
}
v = sink;
while(v != source) {
int u = parent[v];
flow[u][v] += augment;
flow[v][u] -= augment;
v = u;
}
max_flow += augment;
}
return max_flow;
}
//=====================================================================================
// 7. mst: prim, kruskal (pe un graf neorientat cu costuri)
// usage example (n-ai bani multi, deci vrei cost minim?):
// graf_neorientat g(4);
// g.adauga_muchie(0,1,5);
// g.adauga_muchie(1,2,3);
// int cost_prim = g.prim();
// int cost_kruskal = g.kruskal();
//=====================================================================================
class graf_neorientat {
private:
int n;
vector<vector<pair<int,int>>> adj;
public:
graf_neorientat(int n) : n(n) {
adj.resize(n);
}
void adauga_muchie(int u, int v, int cost) {
adj[u].push_back({v, cost});
adj[v].push_back({u, cost});
}
// prim
int prim(int start = 0) {
vector<int> viz(n, 0);
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, start});
int total_cost = 0;
while(!pq.empty()) {
auto [c, node] = pq.top();
pq.pop();
if(viz[node]) continue;
viz[node] = 1;
total_cost += c;
for(auto &ed : adj[node]) {
if(!viz[ed.first]) {
pq.push({ed.second, ed.first});
}
}
}
return total_cost;
}
// kruskal
struct dsu {
vector<int> par, rnk;
dsu(int n) : par(n), rnk(n, 0) {
for(int i = 0; i < n; i++) par[i] = i;
}
int find(int x) {
if(par[x] == x) return x;
return par[x] = find(par[x]);
}
bool unite(int a, int b) {
a = find(a);
b = find(b);
if(a == b) return false;
if(rnk[a] < rnk[b]) swap(a, b);
par[b] = a;
if(rnk[a] == rnk[b]) rnk[a]++;
return true;
}
};
int kruskal() {
vector<tuple<int,int,int>> edges;
for(int u = 0; u < n; u++) {
for(auto &p : adj[u]) {
int v = p.first;
int c = p.second;
if(u < v) {
edges.push_back({c, u, v});
}
}
}
sort(edges.begin(), edges.end(),
[](auto &a, auto &b) { return get<0>(a) < get<0>(b); });
dsu d(n);
int total_cost = 0;
for(auto &e : edges) {
int c, u, v;
tie(c, u, v) = e;
if(d.unite(u, v)) {
total_cost += c;
}
}
return total_cost;
}
vector<vector<pair<int,int>>> getAdj() {
return adj;
}
// cate varfuri (minim) sunt intre nodurile nod1 si nod2
// usage example (daca vrei distanta in numar de noduri intre 2 capete):
// unsigned dist = g.distanta_dintre_noduri(0,2);
unsigned distanta_dintre_noduri(unsigned nod1, unsigned nod2) {
unsigned distanta = 0;
vector<int> viz(n, 0);
queue<pair<int, int>> q;
q.push({nod1, 0});
viz[nod1] = 1;
while(!q.empty()) {
auto [nod, dist] = q.front();
q.pop();
if(nod == (int)nod2) {
distanta = dist;
break;
}
for(auto &vecin : adj[nod]) {
if(!viz[vecin.first]) {
viz[vecin.first] = 1;
q.push({vecin.first, dist + 1});
}
}
}
return distanta;
}
};
//=====================================================================================
// 8. dijkstra - o(e log v)
// usage example (te dai barosan si vrei cea mai scurta distanta dintr-un nod spre rest?):
// vector<vector<pair<int,int>>> adj(5);
// adj[0].push_back({1,10});
// vector<int> distante = dijkstra(adj, 0);
//=====================================================================================
vector<int> dijkstra(const vector<vector<pair<int,int>>> &adj, int start) {
int n = adj.size();
vector<int> dist(n, INT_MAX);
dist[start] = 0;
priority_queue<pair<int,int>, vector<pair<int,int>>, greater<pair<int,int>>> pq;
pq.push({0, start});
while(!pq.empty()) {
auto [cd, node] = pq.top();
pq.pop();
if(cd > dist[node]) continue;
for(auto &edge : adj[node]) {
int vecin = edge.first;
int cost = edge.second;
if(dist[node] + cost < dist[vecin]) {
dist[vecin] = dist[node] + cost;
pq.push({dist[vecin], vecin});
}
}
}
return dist;
}
//=====================================================================================
// 9. bellman-ford - o(v*e)
// usage example (cand ai costuri negative, da' nu cicluri negative):
// vector<tuple<int,int,int>> edges;
// edges.push_back({0,1,5});
// vector<int> d = bellman_ford(5, 0, edges);
//=====================================================================================
vector<int> bellman_ford(int n, int start, vector<tuple<int,int,int>> &edges) {
vector<int> dist(n, INT_MAX);
dist[start] = 0;
for(int i = 0; i < n - 1; i++) {
for(auto &e : edges) {
int u, v, c;
tie(u, v, c) = e;
if(dist[u] != INT_MAX && dist[u] + c < dist[v]) {
dist[v] = dist[u] + c;
}
}
}
return dist;
}
//=====================================================================================
// 10. floyd-warshall - o(v^3)
// usage example (vrei distantele intre toate perechile, boss):
// vector<vector<int>> mat = {{0,5,9999},{9999,0,2},{9999,9999,0}};
// floyd_warshall(mat);
//=====================================================================================
void floyd_warshall(vector<vector<int>> &mat) {
int n = mat.size();
for(int k = 0; k < n; k++) {
for(int i = 0; i < n; i++) {
for(int j = 0; j < n; j++) {
if(mat[i][k] < INT_MAX && mat[k][j] < INT_MAX) {
mat[i][j] = min(mat[i][j], mat[i][k] + mat[k][j]);
}
}
}
}
}
//=====================================================================================
// 11. levenshtein distance (edit distance)
// usage example (vrei sa vezi cate operatii difera doua stringuri):
// int d = levenshtein_distance("bai","ratoi");
//=====================================================================================
int levenshtein_distance(const string &s1, const string &s2) {
int n = s1.size(), m = s2.size();
vector<vector<int>> dp(n + 1, vector<int>(m + 1, 0));
for(int i = 0; i <= n; i++) dp[i][0] = i;
for(int j = 0; j <= m; j++) dp[0][j] = j;
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= m; j++) {
if(s1[i - 1] == s2[j - 1]) {
dp[i][j] = dp[i - 1][j - 1];
} else {
dp[i][j] = 1 + min({dp[i - 1][j], dp[i][j - 1], dp[i - 1][j - 1]});
}
}
}
return dp[n][m];
}
//=====================================================================================
// 12. sortari (mergesort, quicksort) si cautare binara
// usage example (cand vrei sa fii rapid si ordonat, stapane):
// vector<int> arr = {3,1,2};
// merge_sort(arr, 0, arr.size()-1);
// int pos = binary_search_custom(arr, 2);
//=====================================================================================
void merge_sort(vector<int> &arr, int left, int right) {
if(left >= right) return;
int mid = (left + right) / 2;
merge_sort(arr, left, mid);
merge_sort(arr, mid + 1, right);
vector<int> temp;
int i = left, j = mid + 1;
while(i <= mid && j <= right) {
if(arr[i] < arr[j]) temp.push_back(arr[i++]);
else temp.push_back(arr[j++]);
}
while(i <= mid) temp.push_back(arr[i++]);
while(j <= right) temp.push_back(arr[j++]);
for(int k = left; k <= right; k++) {
arr[k] = temp[k - left];
}
}
int partition_qs(vector<int> &arr, int low, int high) {
int pivot = arr[high];
int i = low - 1;
for(int j = low; j < high; j++) {
if(arr[j] < pivot) {
i++;
swap(arr[i], arr[j]);
}
}
swap(arr[i + 1], arr[high]);
return i + 1;
}
void quicksort(vector<int> &arr, int low, int high) {
if(low < high) {
int pi = partition_qs(arr, low, high);
quicksort(arr, low, pi - 1);
quicksort(arr, pi + 1, high);
}
}
int binary_search_custom(const vector<int> &arr, int val) {
int left = 0, right = (int)arr.size() - 1;
while(left <= right) {
int mid = (left + right) / 2;
if(arr[mid] == val) return mid;
else if(arr[mid] < val) left = mid + 1;
else right = mid - 1;
}
return -1;
}
//=====================================================================================
// 13. verificare graf hamiltonian
// usage example (vrei sa vezi daca exista un drum care trece prin toate nodurile):
// vector<vector<int>> adj = {{0,1},{1,0}};
// bool e_hamil = hasHamiltonianPath(adj);
//=====================================================================================
bool hasHamiltonianPath(const vector<vector<int>> &adj) {
int n = (int)adj.size();
vector<vector<bool>> dp(1 << n, vector<bool>(n, false));
for(int v = 0; v < n; v++){
dp[1 << v][v] = true;
}
for(int mask = 0; mask < (1 << n); mask++){
for(int v = 0; v < n; v++){
if(!dp[mask][v]) continue;
for(int next = 0; next < n; next++){
if(!(mask & (1 << next)) && adj[v][next] == 1) {
int nextMask = mask | (1 << next);
dp[nextMask][next] = true;
}
}
}
}
int fullMask = (1 << n) - 1;
for(int v = 0; v < n; v++){
if(dp[fullMask][v]) {
return true;
}
}
return false;
}
//=====================================================================================
// 14. verificare daca e arbore (graf neorientat conex fara cicluri)
// usage example (bagi un graf si vrei sa stii daca e copac?):
// vector<vector<int>> adj(3);
// adj[0] = {1};
// adj[1] = {0,2};
// bool e_arb = isTree(adj);
//=====================================================================================
bool isTree(const vector<vector<int>> &adj) {
int n = (int)adj.size();
vector<int> viz(n, 0);
function<bool(int,int)> dfs = [&](int node, int parent) {
viz[node] = 1;
for(auto &vecin : adj[node]) {
if(viz[vecin] == 0) {
if(dfs(vecin, node) == false) return false;
} else if(vecin != parent) {
return false;
}
}
return true;
};
if(dfs(0, -1) == false) return false;
for(int i = 0; i < n; i++){
if(viz[i] == 0) return false;
}
return true;
}
//=====================================================================================
// 15. lowest common ancestor (lca)
// usage example (cauti stramosul comun, stapane?):
// vector<vector<int>> adj(4);
// adj[0].push_back(1);
// lca l(4, adj, 0);
// int ancestor = l.get_lca(1,2);
//=====================================================================================
class LCA {
public:
int n, LOG;
vector<vector<int>> up;
vector<int> depth;
LCA(int n, vector<vector<int>> &adj, int root = 0) : n(n) {
LOG = log2(n) + 1;
up.assign(n, vector<int>(LOG, -1));
depth.assign(n, 0);
dfs(root, -1, adj);
}
void dfs(int node, int parent, vector<vector<int>> &adj) {
up[node][0] = parent;
for(int i = 1; i < LOG; i++) {
if(up[node][i - 1] != -1)
up[node][i] = up[up[node][i - 1]][i - 1];
}
for(int v : adj[node]) {
if(v != parent) {
depth[v] = depth[node] + 1;
dfs(v, node, adj);
}
}
}
int get_lca(int u, int v) {
if(depth[u] < depth[v]) swap(u, v);
for(int i = LOG - 1; i >= 0; i--) {
if(up[u][i] != -1 && depth[up[u][i]] >= depth[v])
u = up[u][i];
}
if(u == v) return u;
for(int i = LOG - 1; i >= 0; i--) {
if(up[u][i] != up[v][i]) {
u = up[u][i];
v = up[v][i];
}
}
return up[u][0];
}
};
//=====================================================================================
// 16. centroid decomposition
// usage example (cand vrei sa faci chestii avansate pe arbore, bosule):
// vector<vector<int>> adj(5);
// centroiddecomposition cd(5, adj);
//=====================================================================================
class CentroidDecomposition {
public:
int n;
vector<vector<int>> adj, tree;
vector<int> subtree;
vector<bool> removed;
CentroidDecomposition(int n, vector<vector<int>> &adj) : n(n), adj(adj) {
tree.resize(n);
removed.assign(n, false);
subtree.assign(n, 0);
build(0, -1);
}
int find_centroid(int node, int parent, int size) {
for(int v : adj[node]) {
if(v != parent && !removed[v] && subtree[v] > size / 2)
return find_centroid(v, node, size);
}
return node;
}
void calc_subtree(int node, int parent) {
subtree[node] = 1;
for(int v : adj[node]) {
if(v != parent && !removed[v]) {
calc_subtree(v, node);
subtree[node] += subtree[v];
}
}
}
void build(int node, int parent) {
calc_subtree(node, -1);
int centroid = find_centroid(node, -1, subtree[node]);
removed[centroid] = true;
if(parent != -1) tree[parent].push_back(centroid);
for(int v : adj[centroid]) {
if(!removed[v]) build(v, centroid);
}
removed[centroid] = false;
}
};
//=====================================================================================
// 17. heavy-light decomposition (hld) - implementare completa
// usage example (daca vrei query de tip sum pe un arbore, de exemplu):
// heavylightdecomposition hld(n);
// - initializezi cu add edge
// hld.init(0); // root = 0
// hld.build_segment_tree();
// hld.update(u, val); // update un nod
// int ans = hld.query(u,v); // query pe drumul dintre u si v
//=====================================================================================
struct segtree_hld {
int n;
vector<int> st;
segtree_hld(int n) : n(n) {
st.resize(4*n, 0);
}
void build(vector<int> &vals, int idx, int left, int right) {
if(left == right) {
st[idx] = vals[left];
return;
}
int mid = (left+right)/2;
build(vals, idx*2, left, mid);
build(vals, idx*2+1, mid+1, right);
st[idx] = st[idx*2] + st[idx*2+1];
}
void update(int idx, int left, int right, int pos, int val) {
if(left == right) {
st[idx] = val;
return;
}
int mid = (left+right)/2;
if(pos <= mid) update(idx*2,left,mid,pos,val);
else update(idx*2+1,mid+1,right,pos,val);
st[idx] = st[idx*2] + st[idx*2+1];
}
int query(int idx, int left, int right, int ql, int qr) {
if(ql>qr || ql>right || qr<left) return 0;
if(ql<=left && right<=qr) return st[idx];
int mid=(left+right)/2;
return query(idx*2,left,mid,ql,qr) + query(idx*2+1,mid+1,right,ql,qr);
}
};
class HeavyLightDecomposition {
public:
int n;
vector<vector<int>> adj;
vector<int> parent, depth, heavy, size, head, pos;
vector<int> base_array;
segtree_hld *seg;
int curPos;
HeavyLightDecomposition(int n) : n(n) {
adj.resize(n);
parent.resize(n);
depth.resize(n);
heavy.resize(n, -1);
size.resize(n, 0);
head.resize(n);
pos.resize(n);
curPos = 0;
}
void add_edge(int u, int v) {
adj[u].push_back(v);
adj[v].push_back(u);
}
int dfs(int u, int p) {
parent[u] = p;
size[u] = 1;
int mx=-1;
for(auto &v : adj[u]) {
if(v == p) continue;
depth[v] = depth[u] + 1;
int sz = dfs(v,u);
if(sz>mx) {
mx=sz;
heavy[u] = v;
}
size[u]+=sz;
}
return size[u];
}
void decompose(int u, int h) {
head[u] = h;
pos[u] = curPos++;
base_array[pos[u]] = 0; // if you want to store initial node values, place them here
if(heavy[u] != -1) {
decompose(heavy[u], h);
}
for(auto &v : adj[u]) {
if(v==parent[u] || v==heavy[u]) continue;
decompose(v,v);
}
}
void init(int root) {
dfs(root,-1);
base_array.resize(n,0);
decompose(root,root);
}
void build_segment_tree() {
seg = new segtree_hld(n);
seg->build(base_array,1,0,n-1);
}
void update(int u, int val) {
int idx = pos[u];
seg->update(1,0,n-1,idx,val);
}
int query_path(int u, int v) {
int res = 0;
while(head[u] != head[v]) {
if(depth[head[u]] > depth[head[v]]) swap(u,v);
res += seg->query(1,0,n-1,pos[head[v]], pos[v]);
v = parent[head[v]];
}
if(depth[u] > depth[v]) swap(u,v);
res += seg->query(1,0,n-1,pos[u],pos[v]);
return res;
}
int query(int u, int v) {
return query_path(u,v);
}
};
//=====================================================================================
// 18. fenwick tree (bit)
// usage example (vrei update si query rapid pe sume?):
// fenwicktree ft(10);
// ft.update(1,5);
// int s = ft.range_sum(1,3);
//=====================================================================================
class FenwickTree {
vector<int> bit;
int n;
public:
FenwickTree(int n) : n(n) {
bit.assign(n + 1, 0);
}
void update(int idx, int delta) {
for(; idx <= n; idx += idx & -idx)
bit[idx] += delta;
}
int sum(int idx) {
int s = 0;
for(; idx > 0; idx -= idx & -idx)
s += bit[idx];
return s;
}
int range_sum(int l, int r) {
return sum(r) - sum(l - 1);
}
};
//=====================================================================================
// 19. segment tree (completa)
// usage example (cand ai intervale si vrei query/update smecher, stapane):
// segmenttree st(n);
// st.build(arr,1,0,n-1);
// st.update(1,0,n-1,idx,val);
// int rez = st.query(1,0,n-1,l,r);
//=====================================================================================
class SegmentTree {
public:
int n;
vector<int> tree;
SegmentTree(int n) : n(n) {
tree.resize(4*n, 0);
}
void build(vector<int> &arr, int idx, int start, int end) {
if(start == end) {
tree[idx] = arr[start];
return;
}
int mid = (start+end)/2;
build(arr, idx*2, start, mid);
build(arr, idx*2+1, mid+1, end);
tree[idx] = tree[idx*2] + tree[idx*2+1];
}
void update(int idx, int start, int end, int pos, int val) {
if(start == end) {
tree[idx] = val;
return;
}
int mid = (start+end)/2;
if(pos <= mid) update(idx*2, start, mid, pos, val);
else update(idx*2+1, mid+1, end, pos, val);
tree[idx] = tree[idx*2] + tree[idx*2+1];
}
int query(int idx, int start, int end, int left, int right) {
if(left>right || left> end || right<start) return 0;
if(left<=start && end<=right) {
return tree[idx];
}
int mid = (start+end)/2;
int q1 = query(idx*2, start, mid, left, right);
int q2 = query(idx*2+1, mid+1, end, left, right);
return q1 + q2;
}
};
//=====================================================================================
// 20. treap / avl tree / splay tree - exemple minimaliste
// usage example (cand vrei structuri de date mai avansate, stapane):
// ai trei clase: treap, avl, splay. le folosesti cum vrei tu, boss
//=====================================================================================
//-------------------------------------------------------------------------------------
// treap implementation (inserare + cautare)
//-------------------------------------------------------------------------------------
struct TreapNode {
int key, priority;
TreapNode* left;
TreapNode* right;
TreapNode(int key) : key(key), priority(rand()), left(nullptr), right(nullptr) {}
};
class Treap {
public:
TreapNode* root;
Treap() : root(nullptr) {}
TreapNode* rotateRight(TreapNode* y) {
TreapNode* x = y->left;
TreapNode* t2 = x->right;
x->right = y;
y->left = t2;
return x;
}
TreapNode* rotateLeft(TreapNode* x) {
TreapNode* y = x->right;
TreapNode* t2 = y->left;
y->left = x;
x->right = t2;
return y;
}
TreapNode* insertNode(TreapNode* node, int key) {
if(!node) return new TreapNode(key);
if(key < node->key) {
node->left = insertNode(node->left, key);
if(node->left->priority > node->priority) {
node = rotateRight(node);
}
} else {
node->right = insertNode(node->right, key);
if(node->right->priority > node->priority) {
node = rotateLeft(node);
}
}
return node;
}
void insertKey(int key) {
root = insertNode(root, key);
}
bool searchNode(TreapNode* node, int key) {
if(!node) return false;
if(node->key == key) return true;
if(key < node->key) return searchNode(node->left, key);
return searchNode(node->right, key);
}
bool searchKey(int key) {
return searchNode(root, key);
}
};
//-------------------------------------------------------------------------------------
// avl tree implementation (inserare + cautare)
//-------------------------------------------------------------------------------------
struct AVLNode {
int key;
AVLNode* left;
AVLNode* right;
int height;
AVLNode(int key) : key(key), left(nullptr), right(nullptr), height(1) {}
};
class AVL {
public:
AVLNode* root;
AVL() : root(nullptr) {}
int getHeight(AVLNode* node) {
return (node ? node->height : 0);
}
int getBalance(AVLNode* node) {
if(!node) return 0;
return getHeight(node->left) - getHeight(node->right);
}
AVLNode* rotateRight(AVLNode* y) {
AVLNode* x = y->left;
AVLNode* t2 = x->right;
x->right = y;
y->left = t2;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
return x;
}
AVLNode* rotateLeft(AVLNode* x) {
AVLNode* y = x->right;
AVLNode* t2 = y->left;
y->left = x;
x->right = t2;
x->height = max(getHeight(x->left), getHeight(x->right)) + 1;
y->height = max(getHeight(y->left), getHeight(y->right)) + 1;
return y;
}
AVLNode* insertNode(AVLNode* node, int key) {
if(!node) return new AVLNode(key);
if(key < node->key) node->left = insertNode(node->left, key);
else node->right = insertNode(node->right, key);
node->height = 1 + max(getHeight(node->left), getHeight(node->right));
int balance = getBalance(node);
// left left
if(balance > 1 && key < node->left->key) {
return rotateRight(node);
}
// right right
if(balance < -1 && key > node->right->key) {
return rotateLeft(node);
}
// left right
if(balance > 1 && key > node->left->key) {
node->left = rotateLeft(node->left);
return rotateRight(node);
}
// right left
if(balance < -1 && key < node->right->key) {
node->right = rotateRight(node->right);
return rotateLeft(node);
}
return node;
}
void insertKey(int key) {
root = insertNode(root, key);
}
bool searchNode(AVLNode* node, int key) {
if(!node) return false;
if(node->key == key) return true;
if(key < node->key) return searchNode(node->left, key);
else return searchNode(node->right, key);
}
bool searchKey(int key) {
return searchNode(root, key);
}
};
//-------------------------------------------------------------------------------------
// splay tree implementation (inserare + cautare + splay)
//-------------------------------------------------------------------------------------
struct SplayNode {
int key;
SplayNode* left;
SplayNode* right;
SplayNode(int key) : key(key), left(nullptr), right(nullptr) {}
};
class SplayTree {
public:
SplayNode* root;
SplayTree() : root(nullptr) {}
SplayNode* rightRotate(SplayNode* x) {
SplayNode* y = x->left;
x->left = y->right;
y->right = x;
return y;
}
SplayNode* leftRotate(SplayNode* x) {
SplayNode* y = x->right;
x->right = y->left;
y->left = x;
return y;
}
// splay operation: bring key to root
SplayNode* splay(SplayNode* root, int key) {
if(!root || root->key == key) return root;
// key < root->key
if(key < root->key) {
if(!root->left) return root;
// zig-zig
if(key < root->left->key) {
root->left->left = splay(root->left->left, key);
root = rightRotate(root);
}
// zig-zag
else if(key > root->left->key) {
root->left->right = splay(root->left->right, key);
if(root->left->right) {
root->left = leftRotate(root->left);
}
}
return (!root->left) ? root : rightRotate(root);
}
else {
if(!root->right) return root;
// zig-zig
if(key > root->right->key) {
root->right->right = splay(root->right->right, key);
root = leftRotate(root);
}
// zig-zag
else if(key < root->right->key) {
root->right->left = splay(root->right->left, key);
if(root->right->left) {
root->right = rightRotate(root->right);
}
}
return (!root->right) ? root : leftRotate(root);
}
}
SplayNode* insertNode(SplayNode* root, int key) {
if(!root) return new SplayNode(key);
root = splay(root, key);
if(root->key == key) return root;
SplayNode* newNode = new SplayNode(key);
if(key < root->key) {
newNode->right = root;
newNode->left = root->left;
root->left = nullptr;
} else {
newNode->left = root;
newNode->right = root->right;
root->right = nullptr;
}
return newNode;
}
void insertKey(int key) {
root = insertNode(root, key);
}
bool searchKey(int key) {
root = splay(root, key);
return (root && root->key == key);
}
};
#endif // CHEATSHEET_H
// exemplu minimal in main, daca vrei sa testezi ceva:
int main() {
}
Editor is loading...
Leave a Comment