This approach does work. A "Binary-Indexed-Tree" is just an implicit balanced binary tree with some extra "compression". See this answer for the details on how and why this is done, but essentially the purpose is just to run in fewer cycles.
Your approach works fine asymptotically and will probably even perform fine in practice.
First, is the resulting tree produced by your queue always guaranteed to be "short"? The answer is yes. The easiest way to see this is notice that your queue's use is naturally into "epochs", where each epoch builds roughly one level of the tree.
First, as a simplification, don't bother tracking the
marked separately from the others. Instead, just repeat the loop until
Q has only one element, and then let that be your root. This simplifies your state and makes it easier to follow.
while q.size() > 1:
next = 
while q.size() > 0:
a := q.pop()
b := q.pop()
for v in next:
root := q.pop()
If the queue contains all $n$ before an iteration, then afterwards it will contain either $\lfloor n / 2 \rfloor$ or $\lfloor n / 2 \rfloor + 1$ nodes depending on whether $n$ is is even or odd.
In addition, the maximum height of the nodes in the array will increase by at most one, since each node is only paired with one other (a careful analysis will show it always increases by exactly one, but we don't actually care).
The first observation tells us that the loop will run for $O(\log n)$ iterations. The second therefore tells us that the resulting tree will have height at most $O(\log n)$ since the height of the trees in the queue increase by at most 1 every iteration.
So the tree may not be perfectly "balanced", but its height is still bounded by $O(\log n)$ and thus any operation that runs in time bounded by the tree's height will run in $O(\log n)$ time.
The fact that I recursively explore right and left. Intuition tells me that because there are "enough" cases where the descent is stopped it's OK but couldn't find a way to formalize/prove it.
This is actually straightforward. Suppose your tree has nodes in some levels that look the below, where the
[--...--] indicate the range of values in the original array that the node represents.
Corresponding queries will be drawn with
(...) instead. There are (generically) only a few kinds to worry about:
(- - Q1 - -)
(- - Q2 - -)
(- - Q3 - -)
(- - - - - Q4 - - - -)
(- - - - - - - - Q5 - - - - - - - - - - -)
Note that Q2 and Q4 have a symmetric forms that I'm omitting.
- Q1 only traverses the left half
- Q2 only traverses the left half
- Q3 traverses both halves
- Q4 traverses both halves
- Q5 covers the entire range, so it won't traverse either
Thus we only really need to analyze Q3 and Q4.
Q4 totally covers the right half, so that "traversal" is guaranteed to be constant. So only the left half is traverses to any non-constant depth.
Thus the only "interesting" case is the Q3-type query, which only partially crosses the left child range and the right child range.
Note that the type-Q3 query extends to the left edge of the right child, and to the right edge of the left child.
This means that in the subtrees, there will be no type-Q3 queries, which can't extend to either edge. All queries will either completely miss each node, completely cover them, or extend past an edge.
So there will be at most one type-Q3 query in the entire tree (note that type Q5 also check both children, but that they are "fast").
Since there can only be one of them, you can essentially ignore them in the analysis - at most $O(\log n) + O(\log n) = O(\log n)$ nodes will be visited.