Introduction to Segment Trees (Range Minimum Query)

Range Minimum Query

Given an array of length , answer qeuries. should return the index , where .

There are many ways to do this. In the case where 's element values are allowed to change, and yet we have to maintain to work correctly, a segment tree is our best option. Follows is a brief explanation of segment trees for this specific example. I'll put a more generalized explanation in another post.

Segment Trees

The idea behind a segment tree is to build a binary tree where each node represents a segment of . For Range Minimum Query, each tree node will contain the value of (the index of the minimum value in the node’s segment of the array).

Now, how are nodes and segments assigned? For simplicity, let’s assume that ‘s length is a power of two:

• Starting at the lowest level of the tree, we’ll have leaf nodes each representing an element of . As shown in the following figure, if we label leaf nodes from to from left to right, each node will contain the value .
• For each internal node starting from the bottom, we compute as follows: . Meaning, a parent node will get the value of one of its children such that is minimum.
• Since this is a binary tree with the last level having nodes, the tree will have the height of . Level will have one node, the root, which holds . This means that each node on a level will represent a segment of length .

The implementation is going to be straight forward from here on. We’ll represent the tree as an array tree of length 2 << ceil(log2(N + 1)). Node i has a left child 2 * i and a right child 2 * i + 1. On an update(i), we’ll traverse the tree from top to bottom, change array value at when we reach the leaf i, and update the tree as we go back up. On a getMin(range), we’ll recurse from root until we visit all maximal sub-segments of the range and return the required value. Here’s an implementation in C++ with this tutorial as a reference:

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

class segTree {
    // O(n)
    int *array, *tree;
    int arrayLen, treeLen;

    // O(n)
    void initialize(int node, int b, int e) {
        if (b == e)
            tree[node] = b;
        else {
            // recurse
            initialize(2 * node, b, (b + e) / 2);
            initialize(2 * node + 1, (b + e) / 2 + 1, e);
            // update value
            if (array[tree[2 * node]] <= array[tree[2 * node + 1]])
                tree[node] = tree[2 * node];
            else
                tree[node] = tree[2 * node + 1];
        }
    }
public:
    segTree(int *array, int arrayLen) {
        this->arrayLen = arrayLen;
        this->array = array;
        this->treeLen = 2 << (int)ceil(log2(arrayLen));
        cout << "treeLen=" << treeLen << endl;
        this->tree = new int[treeLen];
        memset(tree, -1, sizeof(int) * treeLen);
        initialize(1, 0, arrayLen - 1);
    }

    // O(log n)
    void update(int i, int v, int node = 1, int b = 0, int e = 0) {
        e = arrayLen - 1 - e;
        if (b == e) {
            array[i] = v;
        } else {
            int mid = (b + e) / 2;
            if (i <= mid)
                update(i, v, 2 * node, b, arrayLen - 1 - mid);
            else
                update(i, v, 2 * node + 1, mid + 1, arrayLen - 1 - e);
            if (array[tree[2 * node]] <= array[tree[2 * node + 1]])
                tree[node] = tree[2 * node];
            else
                tree[node] = tree[2 * node + 1];
        }
    }

    // O(log n)
    int query(int i, int j, int node = 1, int b = 0, int e = 0) {
        e = arrayLen - 1 - e;
        // bad interval
        if (i > e || j < b)
            return -1;
        // good interval
        if (b >= i && e <= j)
            return tree[node];
        // partial interval
        int left = query(i, j, 2 * node, b, arrayLen - 1 - (b + e) / 2);
        int right = query(i, j, 2 * node + 1, (b + e) / 2 + 1, arrayLen - 1 - e);
        if (left == -1)
            return tree[node] = right;
        if (right == -1)
            return tree[node] = left;
        if (array[left] <= array[right])
            return tree[node] = left;
        return tree[node] = right;
    }
};

int main() {
    int A[10] = { 2, 4, 3, 1, 6, 7, 8, 9, 1, 7 };
    segTree t(A, 10);
    cout << "getMin(0, 4) = " << t.query(0, 4) << endl;
    t.update(1, 0);
    cout << "getMin(0, 4) = " << t.query(0, 4) << endl;
    t.update(0, -1);
    cout << "getMin(0, 4) = " << t.query(0, 4) << endl;
    return 0;
}

10088 – Trees on My Island

Given a polygon whose vertices are of integer coordinates (lattice points), count the number of lattice points within that polygon.
Pick’s theoreom states that
Where

• is the number of lattice points in the interior (this is our program’s output).
• is the area of the polygon.
• is the number of lattice points on the exterior.

All the reqired quantities are easily computable, however, needs some extra work. To find the number of lattice points on line segment , we simply calculate .
C++ implementation with rank 329:

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

typedef long long gtype;
typedef complex<gtype> point;
#define x real()
#define y imag()
#define crs(a, b) ( (conj(a) * (b)).y )

long double polArea(vector<point> & p) {
	long double area = 0;
	for (size_t i = 0; i < p.size() - 1; ++i)
		area += crs(p[i], p[i + 1]);
	return abs(area) * 0.5;
}

long long gcd(long long a, long long b) {
	long long t;
	while (b)
		t = b, b = a % b, a = t;
	return a;
}

long long polLatticeB(vector<point> & p) {
	long long b = 0;
	for (size_t i = 1; i < p.size(); ++i)
		b += gcd(abs(p[i].y - p[i - 1].y), abs(p[i].x - p[i - 1].x));
	return b;
}

int main() {
	int n;
	while (cin >> n && n) {
		// polygons
		vector<point> p(n + 1);
		for (int i = 0; i < n; ++i)
			cin >> p[i].x >> p[i].y;
		p[n] = p[0];
		// is convex
		cout << (long long) (polArea(p) - polLatticeB(p) * 0.5l + 1) << endl;
	}
	return 0;
}

530 – Binomial Showdown

This problem is identical to 369 – Combinations.

369 – Combinations

A combinations problem. Given N and R, find NCR.
There’s a variety of ways; The first two solutions are straight-forward computation of . The last two have some tricks:

A naive Java solution that uses big arithmetic:

import java.math.*;
import java.util.*;

public class Main {

	private static BigInteger C(BigInteger n, BigInteger r) {
		r = (r.compareTo(n.subtract(r)) > 0) ? n.subtract(r) : r;
		BigInteger num = BigInteger.ONE, den = BigInteger.ONE;
		while (!r.equals(BigInteger.ZERO)) {
			num = num.multiply(n); den = den.multiply(r);
			r = r.subtract(BigInteger.ONE); n = n.subtract(BigInteger.ONE);
		}
		return num.divide(den);
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		while (s.hasNext()) {
			BigInteger n = s.nextBigInteger(), r = s.nextBigInteger();
			if (n.equals(BigInteger.ZERO) && r.equals(BigInteger.ZERO))
				break;
			System.out.printf("%s things taken %s at a time is %s exactly.\n", n, r, C(n, r));
		}
	}
}

A similar C++ solution:

#include <cstdio>
#include <algorithm>
#include <cmath>
using namespace std;

unsigned long long C(int n, int r) {
	r = min(n - r, r);
	long long out = 1;
	for (int i = 1; i <= r; ++i) {
		out *= n - r + i;
		out /= i;
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

A slower, but totally accepted, solution reduces the computations as you were doing it by hand; We have two arrays, one for the numerator and another for the denominator. We do a 2D loop to reduce the numerator with respect to the denominator and hence the answer. C++ implementation:

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
using namespace std;

#define REDUCE(a, b) { int g = gcd(a, b); a /= g; b /= g; }

int num[100], den[100];
int numI, denI;

long long gcd(long long a, long long b) {
	long long t;
	while (a) { t = a; a = b % a; b = t; }
	return b;
}

long long C(int n, int r) {
	// fill arrays
	r = min(n - r, r);
	numI = denI = 0;
	while (r) { num[numI++] = n--; den[denI++] = r--; }
	// reduce & compute
	long long out = 1;
	for (int i = 0; i < numI; ++i) {
		for (int j = 0; j < denI; ++j)
			REDUCE(num[i], den[j]);
		out *= num[i];
	}
	return out;
}

int main() {
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, C(n, r));
	return 0;
}

The last solution has the same complexity as the first two. It uses Pascal’s Triangle for computing combinations. C++ implementation:

#include <cstdio>
using namespace std;

#define N 128

long long pascalTri[N * (N + 1) / 2];

void fillPascal() {
	for (int l = 0, lStart = 0; l < N; ++l, lStart += l) {
		pascalTri[lStart] = pascalTri[lStart + l] = 1;
		for (int i = 1; i < l; ++i)
			pascalTri[lStart + i] = pascalTri[lStart + i - l] + pascalTri[lStart + i - l - 1];
	}
}

int main() {
	fillPascal();
	long long n, r;
	while (scanf("%lld %lld", &n, &r) == 2 && n && r)
		printf("%lld things taken %lld at a time is %lld exactly.\n", n, r, pascalTri[n * (n + 1) / 2 + r]);
	return 0;
}

10814 – Simplifying Fractions

A simple math GCD problem with big arithmetic.

• Get fraction a / b.
• Find g : GCD(a, b).
• Divide both a, b by g.
• Output.

Rank 461 Java code:

import java.math.BigInteger;
import java.util.Scanner;

public class Main {

	private static BigInteger gcd(BigInteger a, BigInteger b) {
		BigInteger t;
		while (a.compareTo(BigInteger.ZERO) != 0) {
			t = a;
			a = b.mod(a);
			b = t;
		}
		return b;
	}

	public static void main(String[] args) {
		Scanner s = new Scanner(System.in);
		int n = s.nextInt();
		BigInteger a, b, g;
		while (n-- > 0) {
			a = s.nextBigInteger();
			s.next();
			b = s.nextBigInteger();
			g = gcd(a, b);
			System.out.println(a.divide(g) + " / " + b.divide(g));
		}
	}
}