树状数组及其详细解析支持区间修改与单点查询操作
发布时间
阅读量：
阅读量
在先前发布的博客 《树状数组：单点修改，区间查询（详解）》 中，我已对树状数组进行了详细介绍，并通过一道例题进行了讲解。今日将继续分析另一道相关题目：
题目描述
给定数列 ，你需要依次进行 q个操作，操作有两类：
1 l r x：给定 ，对于所有 ，将 加上 （换言之，将 分别加上 ）；
2 i：给定 ，求 的值。
输入格式：
第一行包含 2 个正整数 ，表示数列长度和询问个数。
第二行 n个整数 ，表示初始数列。
接下来 q 行，每行一个操作，为以下两种之一：
1 l r x：对于所有 ，将 a[r] 加上 x ；
2 i ：给定 i，求 a[i] 的值。
对于每个 2 i 操作，输出一行，每行有一个整数，表示所求的结果。
3 2
1 2 3
1 1 3 0
2 2
2
这道题目与前一题正好呈现相反的特性。针对本题，我们可借助差分数组的理念进行求解。在输入阶段，将差分数组直接构建到树结构中。依据差分数组的特性可知，a[i] 等于 pre[1] 加上 pre[2] 再加上一直到 pre
全部评论 (0)
还没有任何评论哟~