2D, dynamic range tree based on GNU policy-based data structures. X is limited by size, and Y is limited to be distinct for each point.

RangeTree2.cpp

#include <bits/stdc++.h>
using namespace std;

/**
 * 2D, dynamic range tree based on GNU policy-based data structures.
 * Allows for fast, O(lg^2 N) range queries and updates, using O(N lg N) memory.
 * The first dimension must be in the interval [0..sx] passed into the constructor,
 * while the second dimension can be anything. Update adds a point at (x, y),
 * while Query finds the number of unique points with coordinates (x' <= x, y' <= y).
 */
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace __gnu_pbds;
typedef tree<pair<int, int>, null_type, less<pair<int, int> >, rb_tree_tag,
             tree_order_statistics_node_update> ordered_set;
class RangeTree {
	int sx;
	ordered_set* fenwick;
public:
	RangeTree(int sx) : sx(sx) { fenwick = new ordered_set[sx + 2]; }
	~RangeTree() { delete[] fenwick; }
	void update(int x, int y) {
		for (int i = x + 1; i <= sx + 1; i += i & -i)
			fenwick[i].insert({ y, rand() });
	}
	int query(int x, int y) {
		int result = 0;
		for (int i = x + 1; i; i -= i & -i)
			result += fenwick[i].order_of_key({ y + 1, 0 });
		return result;
	}
	int query(int x1, int y1, int x2, int y2) {
		return query(x2, y2) - query(x2, y1-1) - query(x1-1, y2) + query(x1-1, y1-1);
	}
};

int main() {
	RangeTree rt(9);
	rt.update(0, 0);
	rt.update(4, 5);
	rt.update(8, 2);
	cout << rt.query(0, 0) << endl;
	cout << rt.query(5, 4) << endl;
	cout << rt.query(4, 5) << endl;
	cout << rt.query(9, 9) << endl;
	cout << rt.query(9, 2) << endl;
	cout << rt.query(7, 5) << endl;
	cout << rt.query(1, 1, 9, 5) << endl;
	cout << rt.query(1, 1, 9, 3) << endl;
}