考虑到如果 \(a_i=sum_{i-1}\) 那么前缀和就会在经过 \(i\) 之后翻倍，然后考虑把它转化成 \(a_i>=sum_{i-1}\) 这种形式也同样满足上述性质。
考虑从一个满足 \(a_i>=sum_{i-1}\) 的点 \(i\) 开始寻找，下一个满足 \(a_j>=sum_{j-1}\) 的点 \(j\) 必定满足两个条件。
-
\[i<j \]
-
\[a_j>=2*sum_{i-1} \]
从最小值开始跳，因为最多有 \(\log 1e9\) 个 \(a_i>=sum_{i-1}\)，所以最多跳 \(\log 1e9\) 次。
于是我们对值域维护一个动态开点线段树，线段树中一个权值 \(x\) 存的是权值为 \(x\) 的数的下标，对于一次查询，从最小值开始查询，设上一次寻找到的点的下标为 \(nxt\)，然后每次查询值域大于 \(sum_{nxt-1}\) 的值的下标最小值 \(g\)，需满足 \(nxt<g\)，然后再判断 \(g\) 是否是答案即可。
怎么维护 \(sum\) 数组呢？维护一个树状数组。
如果一个权值对应有多个下标怎么办？在叶子节点上维护一个可删的小根堆即可。