我们如何在每个操作的数组开始处添加元素并计算任何给定范围的总和。

Question

您首先得到一组N整数(1<=N<=105)。鉴于此数组，你必须执行2种操作：

(i) Operation 1 : Op1(l, r) 

您将得到2个整数l和r。 (1 <= l <= r <= current size of the array)。您需要返回l和r（含）之间的所有元素的总和。也就是说，如果数组中当前的元素是a1，a2，a3 .... an，则需要返回以下sum : al + al+1 + al+2 ... + ar。

(ii) Operation 2 : Op2(x) 

给出一个整数x (|x| <= 109)。将此元素添加到数组的开头。在此操作之后，x现在将变为a1，old a1现在将变为a2，依此类推。阵列的大小将增加1。

我使用初始给定数组创建了分段树，并且可以计算范围总和....但是我怎样才能在分段树中添加一个元素并相应地修改它？

Answer 1

对于这种类型的问题，您可以使用数据结构知道作为TREAP（随机二进制搜索树）。 有关更多信息树堆请点击此链接 - cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html

Answer 2

试试这个离线算法： -

先阅读阵列英寸

在所有查询然后读取并存储它们，并且还计数没有类型2的查询，让它成为K.

现在创建一个新数组b长度K +的长度的（a）中。

现在从b中的索引1开始，向后遍历查询，对于每个类型2查询，将其元素添加到数组b中。

现在在数组b上构建一个分段树或二进制索引树。

使用变量c来计算所遇到的类型的2号查询到现在，它初始化为0

然后遍历您的查询列表和2型的每个查询只需1

增加Ç

对于在数组a中具有范围l ... r的类型1的查询，其在数组b中的范围将对应于（l + kc）...（r + kc）。

因此，使用上面构建的分段树或二进制索引树在转换后的范围上回答此查询。 我希望它有帮助。