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

TopCoder – SRM570

Div2 – 250

You’re required to count the number of equal-valued pairs in an array. Get the frequency of each value, divide by two and sum that up.

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

class Chopsticks {
public:
	int getmax(vector <int> length);
};
int Chopsticks::getmax(vector <int> length) {
	map<int, int> freq;
	for (int i = 0; i < length.size(); ++i)
		freq[length[i]]++;
	int ans = 0;
	for (map<int, int>::iterator itr = freq.begin(); itr != freq.end(); ++itr)
		ans += itr->second / 2;
	return ans;
}

Div2 – 500

A simple simulation problem. You’re given a list of commands a that you’re required to follow T times. Output the manhattan distance you have travelled. Each command is an integer that determines the distance you have to travel and the rotation you have to do. After following command i, you have travelled a distance of a[i] and rotated an angle of 90 * a[i] to the right.
The naieve solution is acceptable.

#include <vector>
#include <cmath>
using namespace std;
typedef long long int64;

int dx[4] = { 1, 0, -1, 0 };
int dy[4] = { 0, 1, 0, -1 };

class RobotHerbDiv2 {
public:
	int getdist(int T, vector<int> a);
};
int RobotHerbDiv2::getdist(int T, vector<int> a) {
	int x = 0, y = 0, d = 0;
	for (int j = 0; j < T; ++j) {
		for (int i = 0; i < a.size(); ++i) {
			x += a[i] * dx[d];
			y += a[i] * dy[d];
			d += a[i], d %= 4;
		}
	}
	return abs(x) + abs(y);
}

Div2 – 1000

Given a tree , count the number of its subtrees (a subtree here is any tree ).
Think of this recursively; If we have a tree rooted at node with children and each child has possible subtrees, we need to find is .

We use this last formula recursively to get the number of possible trees rooted at as a function of its children. If we sum that up on all the nodes in the tree, we have counted all the possible subtrees rooted at any node.

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <vector>
#include <map>
using namespace std;

typedef long long int64;

class CentaurCompanyDiv2 {
	vector<map<int, int> > graph;
	long long *dp;
	long long rec(int n);
public:
	long long count(vector<int> a, vector<int> b);
};
long long CentaurCompanyDiv2::rec(int n) {
	if (dp[n])
		return dp[n];
	long long ans = 1;
	for (map<int, int>::iterator itr = graph[n].begin();
				itr != graph[n].end(); ++itr)
		ans *= 1 + rec(itr->first);
	return dp[n] = ans;
}
long long CentaurCompanyDiv2::count(vector<int> a, vector<int> b) {
	graph = vector<map<int, int> >(a.size() + 1);
	for (int i = 0; i <= a.size(); ++i)
		graph[i].clear();
	for (int i = 0; i < a.size(); ++i)
		graph[a[i] - 1][b[i] - 1] = 1;
	dp = (long long *) malloc(graph.size() * sizeof(long long));
	memset(dp, 0, sizeof dp);
	long long ans = 0;
	for (int i = 0; i < graph.size(); ++i)
		ans += rec(i);
	return ans + 1;
}

231 – Testing the CATCHER

A Dynamic Programming problem.
A straight-forward application of the Longest Increasing Sub-sequence algorithm.
Caution!

• Insert a new line between data sets.
• The CATCHER can move forward. i.e Longest Non-Decreasing Sub-sequence is required.

C++ implementation:

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

typedef long long int64;

vector<int> missileH;
vector<int> lis;

int main() {
	int caseI = 0, maxLIS;
	// solve
	while (true) {
		// input
		missileH.clear();
		lis.clear();
		for (int h; cin >> h && h != -1; lis.push_back(1))
			missileH.push_back(h);
		if (!missileH.size())
			break;
		// solve
		maxLIS = 1;
		for (int i = 0; i < missileH.size(); ++i) {
			for (int j = 0; j < i; ++j)
				if (missileH[i] <= missileH[j])
					lis[i] = max(1 + lis[j], lis[i]);
			maxLIS = max(maxLIS, lis[i]);
		}
		// output
		if (caseI)
			cout << endl;
		cout << "Test #" << ++caseI << ":" << endl << 
				"  maximum possible interceptions: " << maxLIS << endl;
	}
	return 0;
}

11420 – Chest of Drawers

A Dynamic Programming combinatorics problem.
You start placing the drawers one by one and each time you decide between locked and unlocked. During this process, keep track of the number of drawers placed so far and the number of secure ones. If both reach your target, count that as one solution. The DP solution:

• State S(n, s, l) – n is number of drawers waiting to be placed, s number of secured drawers required and l whether the previous drawer is locked.
• Transition S(n, s, l) = S(n - 1, s - l, true) + S(n - 1, s, false) – You can place a locked drawer which decreases the number of required secured drawers, if and only if the previous drawer is locked. Placing an unlocked drawer only decreases the number of remaining drawers.

Caution!

• long long isn’t enough!

C++ top-down implementation:

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

#define N 128

unsigned long long nWays[N][N][2];

unsigned long long getNWays(int n, int s, bool l) {
	if (n == 0 && s == 0)
		return nWays[n][s][l] = 1;
	if (s > n || n < 0 || s < 0)
		return 0;
	if (nWays[n][s][l] != -1)
		return nWays[n][s][l];
	return nWays[n][s][l] = getNWays(n - 1, s - l, true) + getNWays(n - 1, s, false);
}

int main() {
	memset(nWays, -1, sizeof nWays);
	int n, s;
	while (cin >> n >> s && n >= 0 && s >= 0)
		cout << getNWays(n, s, true) << endl;
	return 0;
}

118D – Caesar’s Legions

A Dynamic Programming problem.
You’re trying to find the number of permutations of footmen/horsemen that match the given criterion. While you’re permuting, some problems are revisited. That’s when DP comes in handy:

• State S(n1, n2, k1, k2) – You’ve placed n1 footmen and n2 horsemen. The previous soldier is either a part of k1 consecutive footmen or k2 consecutive horsemen.
• Transition S(n1, n2, k1, k2) = S(n1 + 1, n2, k1 + 1, 0) + S(n1, n2 + 1, 0, k2 + 1) – You can either place a footman — which increases the number of consecutive footmen by one and resets the number of consecutive horsemen k2 — or a horseman.

Caution!

• Don’t forget the modulo 10⁸.

C++ implementation but with values decreasing instead of increasing:

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

#define N 128
#define K 16
#define M 100000000

int nWays[N][N][K][K];
int N1, N2, K1, K2;

long long getNWays(int n1, int n2, int k1, int k2) {
	if (n1 < 0 || n2 < 0 || k1 < 0 || k2 < 0)
		return 0;
	if(n1 == 0 && n2 == 0)
		return 1;
	if (nWays[n1][n2][k1][k2] != -1)
		return nWays[n1][n2][k1][k2];
	return nWays[n1][n2][k1][k2] =
			(getNWays(n1 - 1, n2, k1 - 1, K2) + getNWays(n1, n2 - 1, K1, k2 - 1)) % M;
}

int main() {
	memset(nWays, -1, sizeof nWays);
	cin >> N1 >> N2 >> K1 >> K2;
	cout << getNWays(N1, N2, K1, K2) << endl;
	return 0;
}