If p is a point 
  Then
    node := root of $mathcal{T}$
    $d_{mathcal{R}}(p) := 0$
    While node is not a leaf
      Do
        If node.x < p_x
          Then node := right child of node
        Else
          node := left child of node
        $d_{mathcal{R}(p)= $d_{mathcal{R}(p)$+value of node
If $p$ is the top of a square
  Then
    Add p_{x_1} and p_{x_2} to $mathcal{T}$.
    $d_{mathcal{R}}(p) := 0$
    node := root of $mathcal{T}$
    While node is not a leaf
      Do 
        if p_{x_1} $\leq$ node.x
            if parent of node.x $\leq$ p_{x_2}
                increase value of right child by 1
            node := left child of node
        else
            node := right child of node
    node := root of $mathcal{T}$
    While node is not a leaf
        if p_{x_2} $\geq$ node.x
            if parent of node.x $\geq$ p_{x_1}
                increase value of left child by 1
            node := left child of node
        else
            node := right child of node
If $p$ is at the bottem of a square
    Remove the points belonging to the square of $p$ from $\mathcal{T}$.