本文主要介绍线段树维护信息、辅助解决问题的技巧。
维护信息、打标记常见 tricks
区间加区间 gcd
由 \(\gcd(a,b)=\gcd(a,a-b)\)，发现区间加不会影响差分数组。
考虑维护差分数组的区间 gcd，这样每次区间 \([l,r]\) 查询后和 \(a_l\) 求一下 gcd 就行了。
区间有无重复数字 / 拓展到满足和（差、积）条件的点对存在性问题
维护每个数字的出现前驱。 \(pre_i\) 表示 \(a_i\) 上一个相同数字出现在 \(pre_i\) 位置。
每次查询 \(\max_{i=l}^r pre_i \lt l\) 则代表没有重复数字。
可以拓展到求满足和（差、积）条件的点对存在性问题。好抽象的表述，我绝对不会告诉你我自己编的这个名字。
这个给道例题 P6617 查找 Search
题面求的是区间内满足和为定值 \(w\) 的点对的存在性。
可以照搬，维护每个点 \(i\) 的前面满足 \(a_j=w-a_i\) 的 \(j\)。记为 \(pre_i\)
但是这样有问题，发现满足 \(i=pre_j\) 的 \(j\) 不是唯一的，这样更新的时候复杂度错误。
发现存在性问题，找一个最容易的就好了。这是再所有 \(j\) 中，只有最靠近 \(i\) 的才有意义。只维护这一个就好，单点修改时只更新它，时间复杂度还是 \(O(1)\)。