I was reading about possible solutions to the well known problem:

Given array `A`

with length `N`

create a structure that enables

- Answering what is the sum $sum_{k=i}^{j} A(k)$
- Updating $A(k)$

I’ve seen most solutions use binary index tree but was curios whether it’s possible to just use a regular tree that is built using similar qualities.

So given $A = (5, 4, 7, 9, 1)$

I try to construct a tree by creating a tree node for each value that has a start and end (which are just the index in the beginning.

To construct the tree I push all the starting node into a queue $Q$

```
while not Q.empty():
next <- ()
for i in range(Q.size()):
f <- Q.front()
Q.pop()
if Q.empty():
if marker:
parent <- make_parent(f, marker)
next.push(parent)
else:
marker <- f
else:
f2 <- Q.front()
Q.pop()
parent <- make_parent(f, marker)
next.push(parent)
for n in next:
Q.push(n)
```

After the this ends marker will hold the root

(I have working c++ code but I tried to provide something more abstract and simple)

and to get a sum of range I perform the following (assuming I have an array Nodes that holds all the leaves) and that the query starts with the root of the tree that we created above

```
sumRangeNode(int i, int j, Node* n)
if i == j
return Nodes(i)
if n == null
return 0
if j < n->start || i > n->end
return 0;
if i <= n->start && j >= n->end
return n->val
return sumRangeNode(i, j, n->left) + sumRangeNode(i, j, n->right)
```

The question is does it still have the $log(N)$ complexity, I’ve tried to reason about it but struggled with:

- The fact that I might be building a tree with “stragglers” like the $1$ in the example
- 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.