写在前面: 线段树所需要维护的信息应当考虑用父结点和左右子结点的关系进行维护, 且这个父子关系应当是可递归的, 这样才能推广到整棵线段树上. 基于这样的维护关系, 线段树本身的所有操作都是基于递归, 包括查询.
对于维护一段区间的信息, 按照传统的前缀和差分的思想, 如果只是进行单点修改或者区间查询其中之一, 那么在预处理以后\(O(1)\)的时间复杂度是非常快的. 但是一些问题的背景下, 需要我们同时进行这两个操作, 同时我们可能还要维护一些区间的其他信息, 那么时间复杂度将达到\(O(N)\), \(n\)个操作的情况下时间复杂度为\(O(N^2)\). 这时候我们就需要使用一些额外的手段来降低时间复杂度, 那么引入线段树就显得十分必要了.
同树状数组一样, 线段树(Segment Tree)是一种基于分治思想的二叉树结构, 用于在区间上进行信息统计. 但线段树这一数据结构较树状数组更具有通用性.
相比较于树状数组, 线段树所能进行的操作更具有一般性, 对于区间而言, 由于其对于区间支持的操作更多, 其能较容易地维护更多的属性.
首先我们来显式地定义一下线段树, 首先线段树是一棵二叉树. 且
根据上面对于线段树所定义的性质, 可以发现除去整棵树除去最后一层一定是一棵完全二叉树, 且树的深度为\(O(logN)\). 因此, 我们可以按照与二叉堆(优先队列)类似的结点父子2倍编号方法, 即
在实际的线段树实现中, 我们可以将左儿子和右儿子简写为x << 1和x << 1 | 1
尽管在实际的编译中, 2*x和2*x+1会被编译器自动优化为这样的写法, 但是还是需要习惯使用位运算的写法.
至此, 我们知道了我们可以使用一个一维数组来存储一棵线段树, 且从根结点\(1\)开始, 每个结点都存储了一个区间及该区间的信息, 并且知道了每个结点左儿子及其右儿子的获取方式. 接下来我们来讨论如何建立这一棵线段树, 在此之前我们先讨论一下一维数组的大小.
根据上述定义的线段树的性质, 可以发现, 其叶子结点一定是元区间, 故对于一段长度为\(n\)的区间建立线段树,至多有\(n\)个叶子结点. 不妨考虑线段树的倒数第二层结点个数, 其一定小于等于\(n\). 由于线段树本身是一棵二叉树(除去最后一层, 其一定是一棵完全二叉树), 故根据二叉树的性质, 第一层至倒数第三层的结点数之和一定小于等于\(n-1\). 同时可以知道最后一层的结点个数一定小于等于\(2*n\), 故整棵线段树的大小一定小于等于\(4*n-1\). 故一维数组的大小可以取区间长度\(n\)的\(4\)倍, 即\(4*n\).
支持较快地维护和查询一段区间内的信息
线段树支持五个操作
本章会重点介绍线段树对于单点修改和区间查询, 为了实现这两个操作, 我们只会用到前四个操作, 不会用到push down,下一章在区间修改的背景下我们会介绍push down操作.
我们现在详细来看每一个操作
线段树的基本用途是对区间进行维护, 支持查询与修改指令. 给定一个长度为\(N\)的区间\(A = [1,N]\), 我们可以在上面建立一棵线段树, 每个结点都包含了其对应区间的信息(区间的左右端点,需要额外维护的信息). 线段树的二叉树结构可以很方便地从上往下传递信息. 以区间最大值为例, 记\(dat(l,r) = max_{l \leq i \leq r}{A[i]}\), 显然\(dat(l,r) = max(dat(l,mid),dat(mid+1,r))\).
在一般的情况下, 我们可以在建树的时候就将数据维护好(先读入所有的操作和数据), 或者我们可以优先建立一棵空树, 后面边读入数据边进行修改和更新操作.
这里给出建立空树的代码
struct Node {
int l, r;
int v; //每个线段树结点存储对应区间信息,详见定义
} tr[N*4]; // 线段树
void build(int u, int l, int r) { //结点编号, 区间左端点, 区间右端点
tr[u] = {l,r}; //建立空树, 只维护区间
if (l == r) return; //叶结点
int mid = (l+r) >> 1; // 下取整
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r); // 递归建立左子树和右子树
}
对于线段树上的结点, 由于其二叉树的性质. 我们可以让左右儿子来更新一个结点. 例如一个结点的最大值, 我们可以在该结点的左右儿子中取最大值.
void push_up(int u) {
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
单点修改是一条形如\(C\ x\ v\)的指令, 表示把\(A[x]\)的值修改为\(v\), 注意这里\(A[x]\)是原区间, 对应到线段树\(tr[]\)上需要递归寻找对应叶结点, 然后在回溯过程中更新父结点信息, 也是同树状数组一样的思想.(因为我们的线段树是在原区间上建立的二叉树结构, 我们是使用这个结构来维护信息的)
具体来说: 在线段树中, 根结点(编号为\(1\)的结点)是执行各种指令的入口. 我们需要从根结点出发, 递归找到代表区间\([x,x]\)的叶结点, 然后从下往上更新\([x,x]\)以及它的所有祖先结点上保存的信息.
void modify(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) tr[u].v = v; //如果找到了线段树中对应的叶结点, 就修改
else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(u << 1, x, v); // x属于左半区间, 根据线段树的定义, 左半区间属于左子树
else modify (u << 1 | 1, x, v); // x属于右半区间, 根据线段树的定义, 右半区间属于右子树
push_up(u); //push_up操作, 用左儿子和右儿子来更新当前结点信息
}
}
区间查询是一条形如\(Q\ l\ r\)的指令, 例如查询区间\(A\)在\([l,r]\)上的最大值. 我们只需要从根结点开始(note,由于递归, 根结点是线段树一切操作的入口), 递归执行以下过程:
\(1.\) 若\([l,r]\)完全覆盖了当前线段树结点代表的区间, 则立即回溯(因为其被包含, 且存储了其区间最大值信息), 并且该节点所存储的对应信息(例如最大值)就为候选答案. (包含情况)
\(2.\) 若左子结点所代表的区间(左半区间)与\([l,r]\)有重叠部分, 则递归访问左子结点(相交情况).
\(3.\) 若右子结点所代表的区间(右半区间)与\([l,r]\)有重叠部分, 则递归访问右子结点(相交情况)
对于左半区间和右半区间的判别需要参照定义, 即左半区间为\([l,mid]\), 右半区间为\([mid+1,r]\). 由于会有两边都相交的情况, 故要写两个\(if\).
int query(int u, int l, int r) {
if (l >= tr[u].l && tr[u].r <= r) return tr[u].v; // 包含情况
int mid = (tr[u].l + tr[u].r) >> 1;
int v = 0; // sentinel 哨兵
if (l <= mid) v = query(u << 1, l, r); // 左区间相交, 注意是 <= mid
if (mid <= r) v = max(v, query(u << 1 | 1, l, r)); // 右区间相交, 与当前答案取max
return v; // 返回答案
}
我们断言支持单点修改和区间查询的线段树的单次操作的时间复杂度为\(O(logN)\).
对于单点修改, 由于每次只会在左右子树选择一边进行搜索,该断言成立. 不妨只考虑查询操作, 可以发现, 会出现以下几种情况.
\(1.\) \(l \leq tr[u].l \leq tr[u].r \leq r\) (由于被包含, 直接返回)
\(2.\) \(tr[u].l \leq l \leq tr[u].r \leq r\)
\((1)\) \(l > mid\) (只递归右子树)
\((2)\) \(l \leq mid\) (虽然递归两棵子树, 但是由于右半区间被包含, 故会在递归之后直接返回)
\(3.\) 与\(2\)对称.
\(4.\) \(tr[u].l \leq l \leq r \leq tr[u].r\), 即\(l,r\)都位于结点之内
\((1)\) \(l,r\)都位于\(mid\)的一侧, 只会递归一棵子树
\((2)\) \(l,r\)位于\(mid\)的两侧, 递归左右两棵子树.
对此, 由于只有\(4.2\)的情况可能会break我们的断言, 故不妨考虑\(4.2\)的情况. 可以发现在\(4.2\)执行以后, 也就是分别递归左右子树以后, \(4\)的条件将不再会被触发. 因为其需要区间\([l,r]\)被包含在\(tr[u].l\)和\(tr[u].r\)中, 但在\(4.2\)执行以后, 将不会发生这种情况, 故\(4.2\)只会发生一次, 也就是说我们不会进行很多次的左右子树分别递归的情况. 故时间复杂度的断言成立.
在介绍完线段树以后, 不妨来看一个例题.
给定一个正整数数列 a1,a2,…,an，每一个数都在 0∼p−1 之间。
可以对这列数进行两种操作：
1.添加操作：向序列后添加一个数，序列长度变成 n+1；
2.询问操作：询问这个序列中最后 L 个数中最大的数是多少。
程序运行的最开始，整数序列为空。
一共要对整数序列进行 m 次操作。
写一个程序，读入操作的序列，并输出询问操作的答案。
输入格式
第一行有两个正整数 m,p，意义如题目描述；
接下来 m 行，每一行表示一个操作。
如果该行的内容是 Q L，则表示这个操作是询问序列中最后 L 个数的最大数是多少；
如果是 A t，则表示向序列后面加一个数，加入的数是 (t+a) mod p。其中，t 是输入的参数，a 是在这个添加操作之前最后一个询问操作的答案（如果之前没有询问操作，则 a=0）。
第一个操作一定是添加操作。对于询问操作，L>0 且不超过当前序列的长度。
对于添加操作, 由于其至多进行\(m\)次, 我们不妨将其当做在区间\([1,m]\)上的\(n+1\)位置进行修改. 其中\(n\)初始为\(0\). 然后让\(n++\). (注意原序列的下标得与线段树的维护的区间对应, 都得从\(1\)开始)
相对应的对于查询操作, 我们可以基于当前的\(n\)进行查询.
故抽象出的上述的两个操作对应了线段树的单点修改和区间查询, 故本题我们只需要用线段树来维护区间的最大值就行了.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 2e5+10;
typedef long long LL;
int m,p;
struct Node{
int l, r;
int v;
} tr[N*4];
void push_up(int u) {
tr[u].v = max(tr[u << 1].v, tr[u << 1 | 1].v);
}
void build(int u, int l, int r) {
tr[u] = {l,r};
if (l == r) return;
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
}
int query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) return tr[u].v;
int mid = (tr[u].l + tr[u].r) >> 1;
int v = 0;
if (l <= mid) v = query(u << 1, l, r);
if (r > mid) v = max(v, query(u << 1 | 1, l, r));
return v;
}
void modify(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) tr[u].v = v;
else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
push_up(u);
}
}
int main() {
scanf("%d%d", &m, &p);
build(1,1,m);
int n = 0, last = 0;
int l;
char op[2];
while(m--) {
scanf("%s%d", op, &l);
if (*op == 'Q') {
last = query(1, n - l + 1, n);
printf("%d\n",last);
} else {
modify(1, n + 1, ((LL)l + last) % p); //notice we start from 1 when building the segment tree, for it to have meaning, we need to start
// from n+1;
n++;
}
}
return 0;
}
在上面我们提到线段树可以维护区间的额外信息.
一般的情况下我们可能要存储多个区间的信息, 那么如何来系统地考虑需要维护哪些信息呢?
\(1.\) 我们首先应当考虑维护问题所问的关于区间的信息\(S\), 并且考虑是否能用左右子结点来计算出该信息.如果可以的话, 那么就只需要信息\(S\). 如果不行, 那么我们需要添加并且维护额外的辅助信息\(S_{sub}\)来计算当前区间的信息\(S\). 并且对于维护额外的辅助信息, 我们也需要反复进行步骤\(1.\)(考虑是否能用左右子结点计算出该信息), 直到所有辅助信息对于维护信息\(S\)具有完备性.
给定长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
1. 1 x y，查询区间 [x,y] 中的最大连续子段和，即 maxx≤l≤r≤y{∑i=lrA[i]}。
2. 2 x y，把 A[x] 改成 y。
对于每个查询指令，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行每行 3 个整数 k,x,y，k=1 表示查询（此时如果 x>y，请交换 x,y），k=2 表示修改。
输出格式
对于每个查询指令输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000,
−1000≤A[i]≤1000
可以看到题目要求单点修改以及区间查询信息, 我们可以使用线段树来实现这些操作.
我们需要查询区间\([x,y]\)的最大连续子段和, 那么线段树上的每一个结点需要维护的信息\(S\)就是最大连续子段和.
现在考虑如果只维护这一个信息是否具有完备性. 不妨考虑线段树的任意一个内部结点\(u\), 考虑其两个左右子结点分别\(l,r\). 可以发现, 如果只维护一个区间的最大连续子段和是不完备的, 因为可能存在中间连续部分是最大连续子段和的情况. 即左区间的后缀和右区间前缀拼接后是最大连续子段和的情况, 故我们需要额外存储辅助信息. 即左区间的最大后缀和以及右区间的最大前缀和, 即这两个信息为\(S_{sub}\)
现在不妨考虑添加\(S_{sub}\)后是否具有完备性, 我们首先考虑\(S_{sub}\)的维护, 即是否能用左右子结点来维护\(S_{sub}\). 不妨仍考虑上面描述的父结点和左右子结点.可以发现左右区间以及前后缀是对称的, 不妨考虑维护最大前缀和的情况. 可以发现\(u\)的最大前缀和只有两种情况, 第一种情况是\(l\)的最大前缀和, 第二种情况包含\(l\)再拼接上\(r\)的最大前缀和. 我们可以在这两种情况中取最大值. 最大后缀同理. 而这里的包含\(l\)就是左子区间的和, 记为\(sum\). 可以发现如果有了\(sum\), 那么维护信息\(S\)就具有完备性了.
再来考虑\(sum\), 我们可以发现其也能通过左右子结点维护, 即取左右儿子的和就行.
故我们讨论完了所需要存储的信息, 接下来可以讨论各个操作的实现.
对于\(build\)操作, 我们需要在建树过程中就进行维护. 对于\(push\_up\)操作, 我们需要通过左右儿子结点算出父结点信息, 即上述所描述的信息. 对于\(modify\)操作, 单点修改同理, 修改完叶子结点后在回溯的过程中push_up更新父结点信息就行.
对于\(query\)操作, 我们仍需要以根结点作为入口, 递归地查询. 这里我们不妨只考虑某一个父子结点对.
\(1.\)可以发现如果若当前父结点被包含了的话, 可以直接返回连续区间和.
\(2.\) 否则, 考虑与当前区间相交的情况(我们并不需要考虑区间不相交的情况, 因为若一开始若相交后续递归不会出现不相交的情况) 首先考虑只相交一边的情况, 若\(r \leq mid\), 那么返回递归查询左子树的结果, 如果\(l > mid\) 则返回递归查询右子树的结果. 不然的话则表面是相交左右两段, 那么分别返回递归左右子树的结果, 然后取最大值, 这里取最大值可以用临时变量配合push_up操作取个巧.
由于讨论了父子结点对, 且这个结构在线段树中是递归的, 那么上述就是我们的递归框架了.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
const int N = 5e5+10;
int n,m;
int w[N];
struct Node {
int l,r;
int tmax;
int max_prefix, max_suffix;
int sum;
} tr[N * 4];
void push_up(Node &u, Node &l, Node &r) {
u.sum = l.sum + r.sum;
u.max_prefix = max(l.max_prefix, l.sum + r.max_prefix);
u.max_suffix = max(r.max_suffix, r.sum + l.max_suffix);
u.tmax = max(max(l.tmax, r.tmax), l.max_suffix + r.max_prefix);
}
void push_up(int u) {
push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
if (l == r) tr[u] = {l, r, w[l], w[l], w[l], w[l]};
else {
tr[u] = {l, r};
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
push_up(u);
}
}
void modify(int u, int x, int v) {
if (tr[u].l == x && tr[u].r == x) tr[u] = {x, x, v, v, v, v};
else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
push_up(u);
}
}
Node query(int u, int l, int r) { // 为了维护的方便, 不妨返回结点信息
if (l <= tr[u].l && tr[u].r <= r) return tr[u];
else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else {
Node l_node = query(u << 1, l, r);
Node r_node = query(u << 1 | 1, l, r);
Node res;
push_up(res, l_node, r_node);
return res;
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%d",&w[i]);
}
build(1,1,n);
while (m--) {
int k, x, y;
scanf("%d %d %d", &k, &x, &y);
if (k == 1) {
if (x > y) swap(x,y);
int res = query(1, x, y).tmax;
printf("%d\n", res);
} else {
modify(1, x, y);
}
}
return 0;
}
在一般情况下在线段树中涉及到区间修改的操作需要使用懒标记(Lazy Tag/Propagation), 但是如果区间修改的操作只涉及到给区间添加一个数的话, 我们可以使用差分的思想, 将其抽象成单点修改和单点查询的操作, 故在此情况下, 我们可以不用使用懒标记, 仍然可以使用本章所介绍的其他操作构建和使用线段树.
如果是区间整体变成一个数, 或是区间整体乘以一个数之类的区间修改操作, 那么我们就需要考虑使用懒标记了.
给定一个长度为 N 的数列 A，以及 M 条指令，每条指令可能是以下两种之一：
C l r d，表示把 A[l],A[l+1],…,A[r] 都加上 d。
Q l r，表示询问 A[l],A[l+1],…,A[r] 的最大公约数(GCD)。
对于每个询问，输出一个整数表示答案。
输入格式
第一行两个整数 N,M。
第二行 N 个整数 A[i]。
接下来 M 行表示 M 条指令，每条指令的格式如题目描述所示。
输出格式
对于每个询问，输出一个整数表示答案。
每个答案占一行。
数据范围
N≤500000,M≤100000,
1≤A[i]≤10^18,
|d|≤10^18
本题需要实现两个操作, 分别是区间加上一个数, 以及查询一个区间的最大公约数.可以看到\(N\)的范围是\(5 \times 10 ^{5}\), 那么任何\(O(NlogN)\) 级别以上的时间复杂度都是不能接受的.
由于涉及到区间的修改和查询, 可以考虑使用线段树来维护.
本题难点有很多, 比如是否需要写懒标记,在区间修改以后如何更新结点的最大公约数, 区间应该存储什么信息.
现在我们一一来看, 首先由上述的线段树 + 差分思想, 本题是可以不用写懒标记的. 只需要在原数组的基础上, 用线段树维护原数组的差分数组就行了(即叶结点维护的信息应该是对应的差分数组). 这样的话, 我们就将区间修改转化为了单点修改和前缀和查询. 在查询的时候只需要求一个前缀和就行了. 对于求前缀和, 我们需要在线段树中存储一个区间和. 将此信息记为\(S_1\), 该信息是完备的, 1不妨考虑一个父结点和左右子结点对, 父结点的和可以用左右子结点各自的和计算出来.
同时由于需要查询区间的最大公约数, 我们还需要在区间存储一个最大公约数, 记为信息\(S_2\), 这也是完备的, 由最大公约数的运算律可知. (最大公约数可以用欧几里得算法求得). 那么由于一个数的最大公约数是其本身, 我们可以很容易的维护叶结点, 并且在回溯过程中维护线段树中所有结点信息. 但是该做法的问题是, 一旦考虑到了前面的区间添加一个数的话, 时间复杂度将会太高. 但是如果只是对于一个点修改的话, 由上面可见, 最大公约数是非常好维护的.
那么自然就会结合上面已经讨论过的转化为差分数组, 此时我们就需要做单点修改, 故上面所有的问题都可以解决. 可是当我们转化为差分数组后, 仍然存在一个问题, 最大公约数该如何计算. 并且就算得到了最大公约数的性质, 使用差分单点修改的话, 最大公约数仍然等价吗?(题目会要求区间加上一个数后求区间最大公约数).
上面的问题可以被《九章算术》中更相减损术回答. 即\(gcd(a,b) = gcd(a, b - a)\), \(gcd(a, b, c)=gcd(a, b - a, c - b)\). 该定理可以被数学归纳法推广到任意变量的情况. 即\(gcd(a_1, a_2, a_3, ..., a_n) = gcd(a_1, a_2 - a_1, a_3 - a_2, ..., a_n)\).
故我们知道了如果转化为差分数组, 则原数组的最大公约数和差分数组等价.
还有最后一个问题, 查询的时候我们是不是仍然需要对于每一个数求一个前缀和(时间复杂度太高), 即, 差分的单点修改方式是否会导致区间的最大公约数被改变, 答案是不会的, 这可以由更相减损术推广.
不妨考虑在区间\([l,r]\)加上一个数\(d\), 即\(gcd(a_l + k, a_{l+1} + k, ..., a_r + k)\). 由更相减损术, 这等价于\(gcd(a_l + k, a_{l + 1} + k - (a_l + k), ..., a_r + k - (a_{r - 1} + k)) \Rightarrow gcd(a_l + k, a_{l + 1} - a_l, ..., a_r - a_{r - 1})\).
故本题我们可以考虑差分的思想, 直接对差分数组进行操作, 在查询的时候, 我们只需要分开查询. 由上面推广后的更相减损术得, 我们只需要让区间的第一个数, 即\(tr[l]\)为操作后的数(因为只有第一个数会被区间修改影响到), 故我们需要用前缀和查询第一个数, 这可以用信息\(S_1\)得到. 其余的\(tr[l + 1] \to tr[r]\)为差分数组的最大公约数就行, 可以通过维护信息\(S_2\)得到.
由于使用了差分, 故在修改的时候应该检查边界的情况.
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
using namespace std;
typedef long long LL;
const int N = 5e5 + 10;
int n, m;
LL w[N];
struct Node {
int l, r;
LL sum, d;
} tr[N * 4];
LL gcd(LL a, LL b) {
if (!b) {
return a;
} else {
return gcd(b, a % b);
}
}
void push_up(Node &u, Node &l, Node &r) {
u.sum = l.sum + r.sum;
u.d = gcd(l.d, r.d);
}
void push_up(int u) {
push_up(tr[u], tr[u << 1], tr[u << 1 | 1]);
}
void build(int u, int l, int r) {
if (l == r) {
LL b = w[l] - w[l - 1];
tr[u] = {l, r, b, b};
} else {
tr[u].l = l, tr[u].r = r;
int mid = (l + r) >> 1;
build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
push_up(u);
}
}
void modify(int u, int x, LL v) {
if (tr[u].l == x && tr[u].r == x) {
tr[u].sum += v;
tr[u].d += v;
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (x <= mid) modify(u << 1, x, v);
else modify(u << 1 | 1, x, v);
push_up(u);
}
}
Node query(int u, int l, int r) {
if (l <= tr[u].l && tr[u].r <= r) {
return tr[u];
} else {
int mid = (tr[u].l + tr[u].r) >> 1;
if (r <= mid) return query(u << 1, l, r);
else if (l > mid) return query(u << 1 | 1, l, r);
else {
Node left = query(u << 1, l, r);
Node right = query(u << 1 | 1, l, r);
Node res;
push_up(res, left, right);
return res;
}
}
}
int main() {
scanf("%d %d", &n, &m);
for (int i = 1; i <= n; i++) {
scanf("%lld", &w[i]);
}
build(1, 1, n);
int l, r;
LL d;
char op[2];
while(m--) {
scanf("%s %d %d", op, &l, &r);
if(*op == 'Q') {
Node l_node = query(1, 1, l);
Node r_node({0,0,0,0});
if (l + 1 <= r) r_node = query(1, l + 1, r); // if only one number is queried
printf("%lld\n", abs(gcd(l_node.sum, r_node.d)));
} else {
scanf("%lld", &d);
modify(1, l, d);
if (r + 1 <= n) modify(1, r + 1, -d); //edge case, only modify if r + 1 <= n, otherwise SE will occur during modify process
}
}
return 0;
}