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 Ai to Aj.

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 Ai to Aj.
If the first integer is 2, the query will continue with U and X. Replace the element at AU with X.

Input:
   N Q
   A1 A2 ... AN

   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
   AN AN-1 AN-2 ... A1

   P1 Q1
   P2 Q2
   ...
   PN QN

#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
   A1 A2 ... AN

#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;
}



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 Wi which connect nodes Pi and Qi, find the shortest path from node S to node E.

Input:
   N E

   P1 Q1 W1
   P2 Q2 W2
   ...
   PM QM WM

#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 Ai and Bi, find the shortest path between two points in each given query of the Q queries.

Input:
   N E
   A1 B1
   A2 B2
   ...
   AE BE

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

int dis[]

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

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
   A1 A2 ... AN

#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';
}


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
   A1 A2 ... AN

#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
   A1 A2 ... AN

#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];
    }
}