Count in Range Solution

function countInRange(nodeL, nodeR, nodeStart, nodeEnd, a, b)
    if nodeR is null or b < nodeStart or nodeEnd < a then
        return 0
    if a <= nodeStart and nodeEnd <= b then
        countR := nodeR.count if nodeR else 0
        countL := nodeL.count if nodeL else 0
        return countR - countL

    mid := (nodeStart + nodeEnd) / 2
    leftCount := countInRange(nodeL.left, nodeR.left, nodeStart, mid, a, b)
    rightCount := countInRange(nodeL.right, nodeR.right, mid + 1, nodeEnd, a, b)
    return leftCount + rightCount

Query: countInRange(roots[l], roots[r + 1], 0, maxVal, a, b)

Time: $O(\log n)$ per query.