Optimize binary search on Segment Tree by storing past result

Question

Goal

Let $A[n]$ be an arbitrary array of integers of length $n$. Let $S$ be a segment tree, represented by an array of records: each record containing the left and right bounds ($[l,r]$) of the segment the node covers, and a "sum" value equal to $\sum_{k=l}^rA_k$. I would like to perform a Weighted Random Selection on $A$, and because $S$ is a balanced binary tree, I can perform a binary search by traversing $S$ and do WRS in $\Theta(\lg n)$ time. In this case, the domain of my random variable $r$ is $[0,\sum_{k=1}^nA_k]$.

Now, suppose I delete the element $A_d,d\in[1,n]$, but because reconstructing $S$ takes $\mathcal{O}(n\lg n)$ time, I choose to let $S$ remain unmodified.

To perform WRS in this case, I am thinking that instead of starting from the first element of $A$, I can start from the $(d+1)$st element, tighten the domain of $r$ to $[0,(\sum_{k=1}^nA_k)-A_d]$ ($A$ here refers to the array before deletion, since the original values are stored in the "sum" values of the leaf nodes of $S$), and wrap back around to the start if I reach the end of $A$ while searching. The trouble is that the nice property of $\Theta(1)$ time needed at each iteration of the binary search (thanks to the balanced binary tree property of $S$) is no longer true. Now, each iteration of the binary search takes $\mathcal{O}(\lg n)$ time (summation over arbitrary segment in $S$), and since the binary search is $\Theta(\lg n)$, WRS done this way takes $\mathcal{O}(\lg^2 n)$ time.

Is it possible to perform WRS on $S$ in $\mathcal{O}(\lg n)$ time while omitting $A_d$?

---

Attempt at a solution

An easy way to make this operation faster is storing the cumulative sum calculated from the last iteration of binary search, and only calculate the ranged sum from the last midpoint to the current midpoint. This halves the size of the segment to be calculated at each iteration. However, this still appears to be in $\mathcal{O}(\lg^2 n)$ time. Halving the size of the segment at each iteration means $\lg(n)+\lg(\frac{n}{2})+\lg(\frac{n}{4})+...+1=\mathcal{O}(\lg \frac{n^{\lg(n)}}{2^{\lg(n)}})=\mathcal{O}(\lg^2 n)$ array accesses.

Answer 1

There turns out to be a very simple way to do this in $\mathcal{O}(\lg n)$:

1. Restrict the domain of $r$ to $[0,(\sum_{k=1}^nA_k)-A_d]$
2. If $r≥\sum_{k=1}^{d-1}A_k$, add $A_d$ to $r$.
3. Search using the original method.

Finding $\sum_{k=1}^{d-1}A_k$ is $\mathcal{O}(\lg n)$ time, finding $A_d$ from $S$ is $\Theta(\lg n)$ time, and the binary search is $\Theta(\lg n)$ time.