<—点个赞吧QwQ
宣传一下算法提高课整理{:target=”_blank”}
线段树
整数问题2 指数级强化版,加法和乘法两种修改操作会产生两种偏移量,并且两者还会互相关联
还是先贴一下 前置知识 以便回顾,只有加法一种偏移量的时候该如何做(本帖中偏移量就是上述帖子中的“懒标记”,由于延迟加载的特性而以“懒”命名,而偏移量对应的是它的实际含义)
接下来我将详细介绍,加法与乘法这两重偏移量,在单独操作的时候如何改变,以及两者之间如何产生关联性(这是对incra原帖的补充)
以上图所示线段树为例,既然有两种操作,并且会产生累加和倍乘两种不同的偏移量,那节点中就应该存在两种对应的偏移量信息$offsetAdd$和$offsetMulti$,在图中用A和M表示,节点在构造时,A初始化为0,M初始化为1
接下来按照需求描述中的指令格式$(op,l,r,c)$,先执行$(2,1,2,1)$,对$[1,2]$区间整体加1,这个时候只要单独处理加法偏移量A,和整数问题2中完全一致
紧接着,执行$(1,1,2,2)$,对$[1,2]$区间整体乘2,下面就有点不一样了:不光要将M乘2,A如果有非0值也要乘2,来看为什么
先对$[1,2]$区间加1之后,值$(1,2)$变成了$(2,3)$,和变成了5,再乘2就变成了$(4,6)$,那这个时候,相比上一次,它应该增加多少呢?答案是2,也就是$1\*2$,因此A要随着M一起乘2
然后,执行一次$(3,1,1)$,查询$pos = 1$位置上现在的值,这个时候需要再次访问到$[1,2]$区间,因此来介绍一下两重$offset$的下传:
首先,仍然是修改区段和,先将孩子节点的$sum$用$offsetMulti$也就是M去乘,再加上孩子节点代表区间的长度乘上$offsetAdd$也就是A的值,就是下传后的$sum = sum * M + A$
接下来,要将两重偏移量全部传给子节点,这个部分就很重要了,引用一下我在Leetcode.1622下写的一条鬼畜Tip,来表明这个地方的规律:
先乘后加可好啦,好处都有啥,说对了就告诉他
先乘后加可好啦,一题能顶两题啦
先乘后加可好啦,每日工资一千八
先乘后加呀,时间不白花,先加后乘呀,写了也白搭
先乘后加可好啦,虽费事,但不挂
面试官真不傻,时间给了他,对面试体验危害大
1622毒瘤啊,我们都要干掉它,先乘后加,17.3%是你啦
这次换一个例子,假设先后执行了$(2,1,4,1),(1,3,4,2),(2,3,4,3),(3,3,3)$,最终查询$pos = 3$位置上 的值,来看一下先加后乘,以及先乘后加之后,A和M以及和该如何变化
显而易见,按照红色的先加后乘,A会出现浮点数,影响处理精度,而绿色的先乘后加不会
于是我们因此得出子节点的$offsetAdd$和$offsetMulti$推导公式:
$offsetMulti = om * M$
$offsetAdd = oa * M + A$
oa和om是子节点原先的加法,乘法偏移量
全部下传完毕后,父节点的偏移量又得分别初始化为0和1
这就是对两重偏移量的原理解释,此外为了满足取模的需求,所有的区间和,偏移量在常规计算完毕之后都要取模,其余实现细节请见注释
C++ 代码
#include <iostream>
#include <algorithm>
using namespace std;
using ll = long long;
struct SegmentTreeNode {
ll left, right, sum, offsetAdd, offsetMulti;
SegmentTreeNode()
: left(0), right(0), sum(0), offsetAdd(0), offsetMulti(1) {}
SegmentTreeNode(ll l, ll r, ll s)
: left(l), right(r), sum(s), offsetAdd(0), offsetMulti(1) {}
};
class SegmentTree {
private:
SegmentTreeNode* base;
ll mod;
//向上传递取模后的和
void pushUp(int p) {
base[p].sum = base[2 * p].sum + base[2 * p + 1].sum;
//以防万一,先取模
base[p].sum %= mod;
}
//向下传递取模后的偏移量
void pushDown(int p) {
int lc = 2 * p, rc = 2 * p + 1;
ll& oa = base[p].offsetAdd, & om = base[p].offsetMulti;
//先修改区间和
base[lc].sum = (base[lc].sum * om + ((base[lc].right - base[lc].left + 1) * oa) % mod) % mod;
base[rc].sum = (base[rc].sum * om + ((base[rc].right - base[rc].left + 1) * oa) % mod) % mod;
//然后按照“先乘后加”规律,处理由乘法和加法带来的偏移量
//乘法偏移量直接乘om
base[lc].offsetMulti = (base[lc].offsetMulti * om) % mod;
base[rc].offsetMulti = (base[rc].offsetMulti * om) % mod;
//加法偏移量需要先乘om再加oa
base[lc].offsetAdd = (base[lc].offsetAdd * om + oa) % mod;
base[rc].offsetAdd = (base[rc].offsetAdd * om + oa) % mod;
//利用引用将两个偏移量初始化
oa = 0;
om = 1;
}
//输入的序列arr只有构造函数中会用到,可以直接复用而不必封装入类
void buildTree(ll* arr, int p, ll l, ll r) {
//构造节点的时候就可以取模了
base[p] = SegmentTreeNode(l, r, arr[l] % mod);
if (l == r) return;
ll mid = (l + r) / 2;
buildTree(arr, 2 * p, l, mid);
buildTree(arr, 2 * p + 1, mid + 1, r);
pushUp(p);
}
//区间加法内核
void addKernel(int p, ll l, ll r, ll c) {
if (l <= base[p].left && r >= base[p].right) {
//这些跟整数问题2的区别只有取模
base[p].offsetAdd = (base[p].offsetAdd + c) % mod;
base[p].sum = (base[p].sum + c * (base[p].right - base[p].left + 1)) % mod;
return;
}
pushDown(p);
ll mid = (base[p].left + base[p].right) / 2;
if (l <= mid) addKernel(2 * p, l, r, c);
if (r > mid) addKernel(2 * p + 1, l, r, c);
pushUp(p);
}
//区间乘法内核
void multiKernel(int p, ll l, ll r, ll c) {
if (l <= base[p].left && r >= base[p].right) {
//加法偏移量要连带着乘c,然后取模
base[p].offsetAdd = (base[p].offsetAdd * c) % mod;
base[p].offsetMulti = (base[p].offsetMulti * c) % mod;
//区间和直接乘就行,与长度无关
base[p].sum = (base[p].sum * c) % mod;
return;
}
pushDown(p);
ll mid = (base[p].left + base[p].right) / 2;
if (l <= mid) multiKernel(2 * p, l, r, c);
if (r > mid) multiKernel(2 * p + 1, l, r, c);
pushUp(p);
}
//查询内核,和整数问题2无差别
ll queryKernel(int p, ll l, ll r) {
if (l <= base[p].left && r >= base[p].right) return base[p].sum;
pushDown(p);
ll mid = (base[p].left + base[p].right) / 2, ans = 0;
if (l <= mid) ans += queryKernel(2 * p, l, r);
if (r > mid) ans += queryKernel(2 * p + 1, l, r);
return ans;
}
public:
SegmentTree(int n, ll* arr, ll p) {
mod = p;
base = new SegmentTreeNode[4 * n + 5];
buildTree(arr, 1, 1, n);
}
~SegmentTree() {
delete[] base;
}
/*
* 再封装了一层用户层面的修改和查询
* 在哪个地址上执行操作是内核层面,而不是用户层面关心的问题
* 就好比各位打开浏览器浏览本题解
* 无需知道操作系统中浏览器任务对应进程的进程id
* 以及操作系统在内存中哪个地址上分配了PCB给此进程
*/
void addRange(ll l, ll r, ll c) {
addKernel(1, l, r, c);
}
void multiRange(ll l, ll r, ll c) {
multiKernel(1, l, r, c);
}
ll queryMod(ll l, ll r) {
//也可以在内核函数中累加ans的时候取模
return (queryKernel(1, l, r) % mod);
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
int n;
ll p;
cin >> n >> p;
//在外部输入序列
ll* arr = new ll[n + 1];
for (int i = 1; i <= n; i++) cin >> arr[i];
//作为参数构造线段树类的对象
SegmentTree ST(n, arr, p);
int m;
cin >> m;
while (m--) {
ll op, t, g, c;
cin >> op >> t >> g;
if (op == 3) {
cout << ST.queryMod(t, g) << '\n';
}
else {
cin >> c;
if (op == 2) ST.addRange(t, g, c);
else ST.multiRange(t, g, c);
}
}
delete[] arr;
return 0;
}