给出一个长为 n 的数列，以及 n 个操作，操作涉及区间加法，单点查值。 输入格式 第一行输入一个数字 n。 第二行输入 n 个数字，第 i 个数字为 a i ​ ，以空格隔开。 接下来输入 n 行询问，每行输入四个数字 o p t opt、 l、 r、 c，以空格隔开。 若 o p t = 0 opt=0，表示将位于 [ , ] [l,r] 的之间的数字都加 c。 若 o p t = 1 opt=1，表示询问 a r ​ 的值（ l 和 c 忽略）。不要暴力C++

算法1

线段树

对于每个节点，维护该节点代表区间的总和sum和区间加值add，查询时将节点代表区间和查询到的add值相加后返回，更新时将add值赋给该节点，并将 add值“打标记”下放至子节点，这样在查询和更新子节点时就可以将父节点的add值加上去了。

时间复杂度

查询和更新都是O(logn)的，共n个数，因此总时间复杂度为O(nlogn)。

参考文献

最长上升子序列问题有nlogn的解法吗？

C++ 代码

算法2

线段树II

对于线段树节点不再维护区间和sum，而是将区间分治成若干部分，每部分维护该部分加的值sum，查询时将节点代表区间分治为若干部分后查询对应部分的sum值并加上区间加值add，更新时将add值标记至左右子节点并累加对应部分的sum值至该节点即可。

参考文献

线段树O(len^2logn)。

C++ 代码