Segment Tree

Segment Tree is a data structure that answers queries of a range efficiently, while being able to be modified.

Given the array A with N elements find the sum of all elements from A_i to A_j.

Each of the Q query consists of 3 integers.
If the first integer is 1, the query will continue with i and j. Print the sum of all elements from A_i to A_j.
If the first integer is 2, the query will continue with U and X. Replace the element at A_U with X.

Input:
   N Q
   A₁ A₂ ... A_N

   1 i j
    or
   2 U X

#include<iostream>
#include<vector>
using namespace std;

vector<int> segTree, a;

void build(int idx, int l, int r) {
    if (l == r) {
        return segTree[idx] = a[l]; // or a[r]
    }
    int mid = (l + r) / 2;

    build(2 * idx, l, mid);
    build(2 * idx + 1, mid + 1, r);

    segTree[idx] = segTree[2 * idx] + segTree[2 * idx + 1];
}

void update(int idx, int l, int r, int u, int x) {
    if (l == r) {
        segTree[idx] = x;
        return;
    }
    int mid = (l + r) / 2;

    if (x <= mid) update(2 * idx, l, mid, u, x);
    else update(2 * idx + 1, mid + 1, r, u, x);

    segTree[idx] = segTree[2 * idx] + segTree[2 * idx + 1];
}

int query(int idx, int l, int r, int x, int y) {
    if (l <= x && y <= r) {
        return segTree[idx];
    } else if (y <= l || x >= r) {
        return 0;
    }
    int mid = (l + r) / 2;

    return query(2 * idx, l, mid, x, y) + query(2 * idx + 1, mid + 1, r, x, y);
}

int main() {
    int n, q; cin >> n >> q;

    for (int i = 0; i < n; i++) cin >> a[i];

    segTree = vector<int>(n);

    build(1, 0, n-1);

    for (int i = 0; i < q; i++) {
        int type, x, y; cin >> type >> x >> y;

        if (type == 1) {
            cout << query(1, 0, n-1, x, y);
        } else {
            update(1, 0, n-1, x, y);
        }
    }
}

Disjoint Set Union

Disjoint Set Union is a data structure that contains elements which point to another element, repeating this process until it reaches the leader, who points to himself.

There are n kingdom.
After every fight between two kingdom, the winner will take the defeated kingdom's resources.
In each fight, the kingdom with more resources will win.

Given the number of kingdoms, their initial resources and the fights,
find the kingdom with the most resources at the end.

Input:
   N M
   A_N A_N-1 A_N-2 ... A₁

   P₁ Q₁
   P₂ Q₂
   ...
   P_N Q_N

#include<iostream>
#include<vector>
using namespace std;
typedef pair<int, int> ii;

#define fi first
#define se second

vector<int> dsu; // resources, the kingdom it is under

int find(int n) {
    if (dsu[n] == n) return n;
    return dsu[n] = find(dsu[n]);
}

void merge(int x, int y) {
    x = find(x); y = find(y);
    if (x == y) return;
    if (dsu[x].fi < dsu[y].fi) {
        swap(x, y);
    }

    dsu[x].fi += dsu[y].fi;
    dsu[y].se = x;
}

int main() {
    int n, m; cin >> n >> m;
    dsu.resize(n);

    for (int i = 0; i < n; i++) {
        cin >> dsu[i].fi;
        dsu[i].se = i;
    }

    for (int i = 0; i < m; i++) {
        int a, b; cin >> a >> b;
        merge(a, b);
    }
}

Minimum Spanning Tree

Minimum Spanning Tree is a data structure that finds the least sum of weights of edges of a weighted graph in order to achieve a goal.

Problem not found...

#include<iostream>
using namespace std;

int main() {}

Dynamic Programming

Dynamic Programming is a method of solving a problem by breaking it down into subproblems and using the results of those subproblems to solve the original problem.

Given an array of size N, find the length of the Longest Increasing Subsequence (Strictly Increasing). 1 <= N <= 80

Input:
N
A₁ A₂ ... A_N

#include<iostream>
#include<vector>
using namespace std;

int main() {
    int n; cin >> n;
    vector<int> v(n), dist(n, 1);

    for (int i = 0; i < n; i++) cin >> v[i];

    for (int i = 1; i < n; i++) {
        for (int j = 0; j < i; j++) {
            if (v[j] < v[i]) {
                dist[i] = max(dist[i], dist[j] + 1);
            }
        }
    }

    int ans = 0;
    for (int i = 0; i < n; i++) {
        ans = max(ans, dist[i]);
    }

    cout << ans << endl;
}

Binary Search

Binary search is a search algorithm that finds the position of a target value within a sorted array.

Given a sorted array of size N and a target value X, find the location of X in the array.

Input:
N X
A₁ A₂ ... A_N

#include<iostream>
using namespace std;

int main() {
    int n, x; cin >> n >> x;
    int a[n];
    for(int i = 0; i < n; i++) {
        cin >> a[i];
    }

    int lf = 0, rg = n-1;
    while (lf < rg) {
        int mid = (lf + rg) / 2;
        if (a[mid] >= x) {
            rg = mid;
        } else {
            lf = mid + 1;
        }
    }
    cout << lf << endl; // or rg
}

Depth First Search - DFS

Depth First Search is a graph traversal algorithm that finds the shortest path from one point to another in an unweighted graph.

Given a graph of N nodes connected by M bidirectional edges which connect nodes P_i and Q_i, find the shortest path from node S to node E.

Input:
   N M
   S E

   P₁ Q₁
   P₂ Q₂
   ...
   P_M Q_M

#include<iostream>
#include<vector>
using namespace std;

vector<vector<int> > adj;
bool visited[n];
const int INF = 1e9;
int S, E;

int dfs(int cur) {
    visited[cur] = true;
    if (cur == E) {
        return 0;
    }
    int res = INF;
    for (int i = 0; i < adj[cur].size(); i++) {
        int next = adj[cur][i];
        if (!visited[next]) {
            int dis = dfs(next);
            if (dis != -1) {
                res = min(res, dis + 1);
            }
        }
    }
    if (res == INF) return -1;
    return res;
}

int main() {
    int n, m; cin >> n >> m;
    visited = vector<int>(n);

    for (int i = 0; i < m; i++) {
        int p, q; cin >> p >> q;
        adj[p].push_back(q);
        adj[q].push_back(p);
    }

    cin >> S >> E;
    cout << dfs(S) << endl;
}

Breadth First Search - BFS

Breadth First Search, just like Depth First Search, is a graph traversal algorithm that finds the shortest path from one point to another in an unweighted graph.

Given a graph of N nodes connected by M bidirectional edges which connect nodes P_i and Q_i, find the shortest path from node S to node E.

Input:
   N M
   S E

   P₁ Q₁
   P₂ Q₂
   ...
   P_M Q_M

#include<iostream>
#include<queue>
using namespace std;
typedef pair<int, int> ii;

#define fi node
#define se dist

int main() {
    int n, m; cin >> n >> m;
    int s, e; cin >> s >> e;

    vector<vector<int> > adj;
    vector<bool> visited;

    for (int i = 0; i < n; i++) {
        int p, q; cin >> p >> q;
        adj[p].push_back(q);
        adj[q].push_back(p);
    }

    queue<int> q;
    q.push_back(ii(s, 0));
    visited[s] = 1;
    while(!q.empty()) {
        ii cur = q.top(); q.pop();
        if (cur.node == e) {
            cout << cur.dist << endl;
            return 0;
        }
        for (int i = 0; i < adj[cur.node].size(); i++) {
            int next = adj[cur.node][i];
            if (!visited[next]) {
                q.push_back(ii(next, cur.dist + 1));
                visited[next] = 1;
            }
        }
    }
}

Dijkstra

Dijkstra's algorithm is an algorithm for finding the shortest paths between nodes in a weighted graph.

Given a weighted graph of N nodes connected by E bidirectional edges with W_i which connect nodes P_i and Q_i, find the shortest path from node S to node E.

Input:
   N E

   P₁ Q₁ W₁
   P₂ Q₂ W₂
   ...
   P_M Q_M W_M

#include<iostream>
#include<vector>
#include<queue>
using namespace std;
typedef pair<int, int> ii;

#define fi node
#define se dist

vector<vector<ii>> adj;
const int INF = 1e9;

int main() {
    int n, e; cin >> n >> e;

    vector<int> distV(n);

    for (int i = 0; i < n; i++) distV[i] = INF;
    for (int i = 0; i < e; i++) {
        int p, q, w; cin >> p >> q >> w;
        adj[p].push_back(ii(q, w));
        adj[q].push_back(ii(p, w));
    }

    priority_queue<ii> q;
    q.push_back(ii(-s, 0));

    while(!q.empty()) {
        ii cur = q.top(); q.pop();
        int curNode = -cur.node;
        int curDist = cur.dist;
        if (curNode == e) {
            cout << curDist << endl;
            return 0;
        }
        for (int i = 0; i < adj[curNode].size(); i++) {
            int next = adj[curNode][i].node;
            int w = adj[curNode][i].dist;
            if (curDist + w < dist[next]) {
                dist[next] = cur.dist + w;
                q.push_back(ii(-next, dist[next]));
            }
        }
    }
}

Floyd Warshall Algorithm

The Floyd Warshall Algorithm is an algorithm for finding shortest paths in a directed weighted graph with positive or negative edge weights (but with no negative cycles).

Given an unweighted graph of N nodes and E bidirectional edges connecting nodes A_i and B_i, find the shortest path between two points in each given query of the Q queries.

Input:
   N E Q
   U₁ V₁ W₁
   U₂ V₂ W₂
   ...
   U_E V_E W_E

   A₁ B₁    A₂ B₂    ...
   A_Q B_Q

#include<iostream>
#include<vector>
using namespace std;

const int INF = 1e9;

int main() {
    int n, e, q; cin >> n >> e >> q;
    int dis[n][n];

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            if (i == j) dis[i][i] = 0;
            else dis[i][j] = INF;
        }
    }

    for (int i = 0; i < e; i++) {
        int u, v, w; cin >> u >> v >> w;
        dis[u][v] = w;
        dis[v][u] = w;
    }

    for (int k = 0; k < n; k++) {
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < n; j++) {
                if (dis[i][k] + dis[k][j] < dis[i][j]) {
                    dis[i][j] = dis[i][k] + dis[k][j];
                }
            }
        }
    }

    for (int i = 0; i < q; i++) {
        int a, b; cin >> a >> b;
        if (dis[a][b] == INF) cout << "-1\n";
        else cout << dis[a][b] << '\n';
    }
}

Bellman Ford Algorithm

The Bellman Ford Algorithm is an algorithm that finds if there is a negative cycle in a graph.

Problem not found...

#include<iostream>
using namespace std;

int main() {}

Quick Sort

Quick Sort is a sorting algorithm that works by selecting a pivot point and then partitioning the array into two subarrays.

Given an array of size N,
Output the array in ascending order.

Input:
N
A₁ A₂ ... A_N

#include <iostream>
#include <vector>
using namespace std;

vector<int> v;
int n;

void quickSort(int l, int r) {
    if (l < r) {
        int pivot = v[r];
        int pivot_ind = l;

        for (int j = l; j <= r - 1; j++) {
            if (v[j] < pivot) {
                swap(v[pivot_ind], v[j]);
                pivot_ind++;
            }
        }
        swap(v[pivot_ind], v[r]);

        quickSort(l, pivot_ind - 1);
        quickSort(pivot_ind + 1, r);
    }
}

int main() {
    cin >> n;
    v = vector<int>(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    quickSort(0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << '\n';
}

Merge Sort

Merge Sort is a sorting algorithm that works like the strategy of divide-and-conquer. It splits the array into two and combining them sorted by repeating the same process on each subset.

Given an array of size N,
Output the array in ascending order.

Input:
N
A₁ A₂ ... A_N

#include <iostream>
#include <vector>
using namespace std;

vector<int> v;
int n;

void mergeSort(int l, int r) {
    if (l == r) return;
    int mid = (l + r) / 2;

    mergeSort(l, mid);
    mergeSort(mid + 1, r);

    vector<is> temp;
    int i = l, j = mid + 1;

    while (i <= mid && j <= r) {
        if (v[i].fi < v[j].fi) temp.push_back(v[i++]);
        else temp.push_back(v[j++]);
    }

    while (i <= mid) temp.push_back(v[i++]);
    while (j <= r) temp.push_back(v[j++]);

    for (int i = l; i <= r; i++) v[i] = temp[i - l];
}

int main() {
    cin >> n;
    v = vector<int>(n);

    for (int i = 0; i < n; i++) {
        cin >> v[i];
    }

    mergeSort(0, n - 1);

    for (int i = 0; i < n; i++) {
        cout << v[i] << " ";
    }
    cout << '\n';
}

Insertion Sort

Insertion sort is a sorting algorithm that places an unsorted element at its suitable place in each iteration.

Given an array A of size N, sort it and output the sorted array.

Input:
N
A₁ A₂ ... A_N

#include<iostream>
using namespace std;

int main() {
    int n; cin >> n;
    int a[n];

    for (int i = 0; i < n; i++) {
    int j = a[i + 1];

    while (j < a[i] && i >= 0) {
      a[i + 1] = a[i];
      --i;
    }
    a[i + 1] = j;
  }

    for (int i = 0; i < n; i++) {
        cout << a[i];
    }
}

Bubble Sort

Bubble Sort is a sorting algorithm that repeatedly compares adjacent elements in each iteration until the array is fully sorted.

Given an array A of size N, sort it and output the sorted array.

Input:
N
A₁ A₂ ... A_N

#include<iostream>
using namespace std;

int main() {
    int n; cin >> n;
    int a[n];

    for (int i = 1; i < n; i++) {
        for (int j = i; j > 0; j--) {
            if (a[j] > a[j-1]) break;
            swap(a[j], a[j-1]);
        }
    }

    for (int i = 0; i < n; i++) {
        cout << a[i];
    }
}

Selection Sort

Selection Sort is a sorting algorithm that is similar to bubble sort but swaps the minimum of what is unsorted in the array with where it is supposed to be instead of swapping adjacent elements if in the wrong order in bubble sort.

Given an array of size N,
Output the array in ascending order.

Input:
N
A₁ A₂ ... A_N

#include<iostream>
using namespace std;

int main() {
    int n; cin >> n;
    int a[n];

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    for (int i = 0; i < n - 1; i++) {
        int cur = i;
        for (int j = i + 1; j < n; j++) {
            if (a[j] < a[cur]) {
                cur = j;
            }
        }
        swap(a[i], a[cur]);
    }

    for (int i = 0; i < n; i++) {
        cout << a[i] << " ";
    }
    cout << '\n';
}

Counting Sort

Counting Sort is a sorting algorithm that uses the frequencies of the values in the input array to determine the order of the values in the output array.

Given a sorted array A of size N, output the array A but sorted in ascending order.

Constraints:
    0 < N <= 100000
    0 <= A[i] <= 100

Input:
   N
   A₁ A₂ ... A_N

#include<iostream>
#include<cstring>
using namespace std;

int main() {
    int n; cin >> n;
    int a[n], freq[100002];
    memset(freq, 0, sizeof(freq));

    for (int i = 0; i < n; i++) {
        cin >> a[i];
        freq[a[i]]++;
    }

    for (int i = 0; i < 100002; i++) {
        for (int j = 0; j < freq[i]; j++) cout << i << " ";
    }

    cout << '\n';
}