src/vs/editor/common/model/intervalTree.ts/searchForEditing
function searchForEditing(T: IntervalTree, start: number, end: number): IntervalNode[] {
	// https://en.wikipedia.org/wiki/Interval_tree#Augmented_tree
	// Now, it is known that two intervals A and B overlap only when both
	// A.low <= B.high and A.high >= B.low. When searching the trees for
	// nodes overlapping with a given interval, you can immediately skip:
	//  a) all nodes to the right of nodes whose low value is past the end of the given interval.
	//  b) all nodes that have their maximum 'high' value below the start of the given interval.
	let node = T.root;
	let delta = 0;
	let nodeMaxEnd = 0;
	let nodeStart = 0;
	let nodeEnd = 0;
	const result: IntervalNode[] = [];
	let resultLen = 0;
	while (node !== SENTINEL) {
		if (getNodeIsVisited(node)) {
			// going up from this node
			setNodeIsVisited(node.left, false);
			setNodeIsVisited(node.right, false);
			if (node === node.parent.right) {
				delta -= node.parent.delta;
			}
			node = node.parent;
			continue;
		}

		if (!getNodeIsVisited(node.left)) {
			// first time seeing this node
			nodeMaxEnd = delta + node.maxEnd;
			if (nodeMaxEnd < start) {
				// cover case b) from above
				// there is no need to search this node or its children
				setNodeIsVisited(node, true);
				continue;
			}

			if (node.left !== SENTINEL) {
				// go left
				node = node.left;
				continue;
			}
		}

		// handle current node
		nodeStart = delta + node.start;
		if (nodeStart > end) {
			// cover case a) from above
			// there is no need to search this node or its right subtree
			setNodeIsVisited(node, true);
			continue;
		}

		nodeEnd = delta + node.end;
		if (nodeEnd >= start) {
			node.setCachedOffsets(nodeStart, nodeEnd, 0);
			result[resultLen++] = node;
		}
		setNodeIsVisited(node, true);

		if (node.right !== SENTINEL && !getNodeIsVisited(node.right)) {
			// go right
			delta += node.delta;
			node = node.right;
			continue;
		}
	}

	setNodeIsVisited(T.root, false);

	return result;
}