programming-examples/java/Data_Structures/QuadTree.java

// https://en.wikipedia.org/wiki/Quadtree
public class QuadTree {

	static class Node {
		int count;
		Node topLeft, topRight, bottomLeft, bottomRight;
	}

	Node root;

	static final int maxx = (1 << 30);
	static final int maxy = (1 << 30);

	// insert point (x,y)
	public void insert(int x, int y) {
		root = insert(root, 0, 0, maxx - 1, maxy - 1, x, y);
	}

	Node insert(Node node, int ax, int ay, int bx, int by, int x, int y) {
		if (ax > x || x > bx || ay > y || y > by)
			return node;
		if (node == null)
			node = new Node();
		++node.count;
		if (ax == bx && ay == by)
			return node;

		int mx = (ax + bx) >> 1;
		int my = (ay + by) >> 1;

		node.bottomLeft = insert(node.bottomLeft, ax, ay, mx, my, x, y);
		node.topLeft = insert(node.topLeft, ax, my + 1, mx, by, x, y);
		node.bottomRight = insert(node.bottomRight, mx + 1, ay, bx, my, x, y);
		node.topRight = insert(node.topRight, mx + 1, my + 1, bx, by, x, y);

		return node;
	}

	// number of points in [x1,x2] x [y1,y2]
	public int count(int x1, int y1, int x2, int y2) {
		return count(root, 0, 0, maxx - 1, maxy - 1, x1, y1, x2, y2);
	}

	int count(Node node, int ax, int ay, int bx, int by, int x1, int y1, int x2, int y2) {
		if (node == null || ax > x2 || x1 > bx || ay > y2 || y1 > by)
			return 0;
		if (x1 <= ax && bx <= x2 && y1 <= ay && by <= y2)
			return node.count;

		int mx = (ax + bx) >> 1;
		int my = (ay + by) >> 1;

		int res = 0;
		res += count(node.bottomLeft, ax, ay, mx, my, x1, y1, x2, y2);
		res += count(node.topLeft, ax, my + 1, mx, by, x1, y1, x2, y2);
		res += count(node.bottomRight, mx + 1, ay, bx, my, x1, y1, x2, y2);
		res += count(node.topRight, mx + 1, my + 1, bx, by, x1, y1, x2, y2);
		return res;
	}

	// Usage example
	public static void main(String[] args) {
		QuadTree t = new QuadTree();

		t.insert(0, 0);
		t.insert(1, 0);
		t.insert(2, 0);
		t.insert(3, 0);
		System.out.println(4 == t.count(0, 0, 3, 0));
	}
}