Optimize binary search on Segment Tree by storing past result
There turns out to be a very simple way to do this in $\mathcal{O}(\lg n)$:


Restrict the domain of $r$ to $[0,(\sum_{k=1}^nA_k)-A_d]$
If $r≥\sum_{k=1}^{d-1}A_k$, add $A_d$ to $r$.
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.