<p>Either consult the <a href="http://www.cgal.org" rel="nofollow">CGAL</a> library or this person's project <a href="http://cgi.di.uoa.gr/~vfisikop/compgeom/Layered_Range_trees/" rel="nofollow">code</a> and <a href="http://arxiv.org/pdf/1103.4521v1.pdf" rel="nofollow">report</a>.</p>

<p>Also, the <a href="http://www.codechef.com/FEB13/problems/TRIQUERY" rel="nofollow">contest</a> is still ongoing, please refrain from asking for help here until the contest is over.</p>
2d Range Search tree for a triangle
<p>I want to implement  2D RANGE TREES for searching given points inside a triangle effectively in O( logn^2 ). </p>

<p>To make things easier,I want to search no of given points which lie in right triangle  with two sides aligned parallel to x-y axis and both sides same. 
So, co-ordinates of vertices of ABC would be A(a,b) , B(a+d,b) , C(a,b+d) and it is a right triangle and AB,AC are parallel to X,Y axis respectively.    </p>

<p>I know i can do this effectively using 2D range trees .(k-d trees O(sqrt(n)) is slow and searching for each point individually is too slow)</p>

<p>Can anyone show me how to implement/explain the algorithm  2D range tree to test which points lie inside above type of triangle?</p>