Skip to content

Instantly share code, notes, and snippets.

@ogzd
ogzd / RMQ.cpp
Last active December 14, 2015 04:08
Range Minimum Query
int rmq[70]; //keeps indices
int ax[10] = {1,4,5,6,7,2,0,3,9,11}; //keeps values
int bx[10]; //keeps node indices for each value in ax
int n;
// init(1, 0, n-1);
void init(int node, int b, int e) {
if(b == e) {
rmq[node] = b;
bx[b] = node;
@ogzd
ogzd / KMP.cpp
Last active December 14, 2015 04:29
KMP String matching
// implementation of Knuth-Morris-Pratt string matching algorithm
// complexity O(n)
// t: text, p: pattern
void kmp(char t[], char p[])
{
int n = strlen(t);
int m = strlen(p);
f[0] = 0;
f[1] = 0;
@ogzd
ogzd / MST.cpp
Last active December 14, 2015 07:19
Kruskal's Algorithm using union-find
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
@ogzd
ogzd / SCC.cpp
Last active December 14, 2015 07:29
Kosaraju's Algorithm for finding SCCs
#include <map>
#include <set>
#include <list>
#include <cmath>
#include <deque>
#include <queue>
#include <stack>
#include <bitset>
#include <cstdio>
#include <vector>
@ogzd
ogzd / BIT.cpp
Created March 3, 2013 13:50
Binary Indexed Tree
#define LOGSZ 17
int tree[(1<<LOGSZ)+1];
int N = (1<<LOGSZ);
// add v to value at x
void add(int x, int v) {
while(x <= N) {
tree[x] += v;
x += (x & -x);
@ogzd
ogzd / stack_queue.cpp
Created March 12, 2013 18:40
Stack & Queue Implementation
class MyStack
{
private:
int pos;
int a[MAXSZ];
public:
MyStack() : pos(0){}
void push(int val)
@ogzd
ogzd / A.java
Created April 15, 2014 20:11
How to write a singleton class
public class A {
private static A a;
// disable new operator
private A() {}
// thread-safe
public static synchronized A get() {
@ogzd
ogzd / recursion.java
Last active August 29, 2015 14:01
How to teach recursion to a 5 years-old
void climbStair()
{
printf("Climbed a stair!");
}
void climbStairs(int stairs)
{
if(stairs > 0)
{
climbStair();
@ogzd
ogzd / v1.cpp
Last active August 29, 2015 14:10
int bs(int* arr, int l, int r, int v)
{
if(l >= r) return -1;
int m = l + (r - l) / 2;
if(arr[m] > v)
{
return bs(arr, l, m, v);
}
if(arr[m] < v)
{
int a[(1 << 17) + 1];
int t[(1 << 17) + 1][18];
// binary function
int f(int a, int b)
{
return a + b;
}
// init segment tree