线段树（2）
写了几个简单题，做一个小的总结。
1.区间修改等差数列
给出一个长度等于 \(r-l+1\) 的等差数列，首项为\(K\)，公差为\(D\)，并将它对应加到 \([l,r]\)范围中的每一个数上。即：令 \(a_l = a_l+K,a_{l+1} = a_{l+1}+K+D...a_r+K+(r-l)*D\)。
其实就是二维差分问题，如果差分数组的首项加\(K\)，末项-\(K\)等价于在这一段区间加上一个\(K\)，那么联想到如果我在差分数组上加上一个D会怎么样？就是加上一个等差数列（详细证明是我队友和说我的，我凭感觉是这样的，然后问的他）。
线段树代码没有差异，注意维护的是差分数组，修改时用下面这段代码修改，\(k\)表示首项，\(d\)表示方差
ll L,R,k,d;cin>>L>>R>>k>>d;
update(L,L,1,1,n,k);
if(L != R)update(L+1,R,1,1,n,d);
if(R+1 <= n)update(R+1,R+1,1,1,n,-k-(R-L)*d);
2.维护方差
其实就是维护平方和，但注意浮点数。
平方和就再维护一个tree2就好了。
注意修改的时候要先修改tree2，再修改tree。
修改的方式就是把 \((x_1+d)^2 变成X_1^2 +2dX_1+d ^2\),再对其求和。其实是一个很简单的修改。
3.维护根号
问题是修改：
接下来 \(m\) 行每行三个整数 k l r。
-
\(k=0\) 表示给 \([l,r]\) 中的每个数开平方（下取整）。
-
\(k=1\) 表示询问 \([l,r]\) 中各个数的和。
其实我有一个很不错的想法，把原数组转换成对数数组，然后开平方就等价于在数组上乘一个\(1/2\),这个问题就转换为了区间乘问题。但是很可惜这题目要求是整数，每次向下取整。这样的话会有很大的损失。目前还没有想到非常好的方法实现这个思路。
这个问题的关键在于数据的特殊性，数据不超过\(1e12\)，连续开方，也就是说不到每个数最多进行10次操作。所有只需要进行一次“剪枝”就好了。
记录区间最值，如果最值小于等于1就不向下访问。
修改的update函数
void update(ll p,ll L,ll R){
if(tree[p].l == tree[p].r){
tree[p].sum = sqrt(tree[p].sum);
tree[p].maxp = sqrt(tree[p].maxp);
return ;
}
ll mid = (tree[p].l+tree[p].r)>>1;
if(tree[ls(p)].maxp > 1 && L <= mid)update(ls(p),L,R);
if(tree[rs(p)].maxp > 1 && mid < R) update(rs(p),L,R);
up(p);
}
4.区间01翻转
其实使用线段树挨个修改也不会有大问题，但是这样写会好一些：
void add(ll p,ll pl,ll pr,ll d){
tag[p] ^= d;//d为1
tree[p] = pr-pl+1-tree[p];
}
对一个01区间而言，前缀和就是区间1的个数，对应的区间长度减1的个数就是0的个数。所以每次都用\((pr-pl+1)-tree[p]\)这样实现一次翻转。
5.区间gcd
与区间求\(max\)，\(min\)相同。
求一个区间的\(max\)就是不断比较两个子区间。那么求\(gcd\)也是一样。
当然这个问题用ST表也可以离线实现，基本一样的将\(max,min\)改为\(gcd\)即可。
下面是ST表的实现
ll Log2[N];//预处理方式，加速方法
void init(){
Log2[0] = -1;//这里是-1注意
for(int i = 1;i <= N;i++) Log2[i] = Log2[i>>1]+1;
for(int i = 1;i <= n;i++) dp_max[i][0]= b[i];
ll p = Log2[n];//轮次
for(int k = 1;k <= p;k++){
for(int s = 1;s + (1<<k) <= n+1;s++){
dp_max[s][k] = gcd(dp_max[s][k-1],dp_max[(n-1,s+(1<<(k-1)))][k-1]);
}
}
}
ll solve(ll l,ll r){
ll k = Log2[r-l+1];
ll x = gcd(dp_max[l][k],dp_max[r-(1<<k)+1][k]);
return x;
}