最初给您一个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 )。将此元素添加到数组的开头。此操作后，xwill now 变为a1，old a1will now 变为a2，依此类推。数组的大小将增加1.
我用初始给定数组制作了段树，并且可以计算范围总和......但是我如何在段树中添加一个元素并相应地修改它？
对于此类问题，您可以使用称为 TREAP（随机二叉搜索树）的数据结构。有关 treap 的更多信息，请点击此链接 - cs.cornell.edu/Courses/cs312/2003sp/lectures/lec26.html
试试这个离线算法：-
首先读入数组a。
然后读入所有查询并存储它们，并计算类型 2 查询的数量，使其为 K。
现在创建一个长度为 K+length of(a) 的新数组 b。
现在从 b 中的索引 1 开始并向后遍历您的查询，对于每个类型 2 查询，将其元素添加到数组 b。
现在在数组 b 上构建一个段树或二进制索引树。
使用变量 c 计算到目前为止遇到的类型 2 查询的数量并将其初始化为 0。
然后遍历您的查询列表，对于类型 2 的每个查询，只需将 c 增加 1。
对于数组 a 中具有范围 l...r 的类型 1 的查询，其在数组 b 中的范围将对应于 (l+kc)...(r+kc)。
所以使用上面构建的分段树或二进制索引树来回答这个关于转换范围的查询。我希望它是有帮助的。