题意分析
首先注意到一个非常特殊的性质，区间查询形如 $\left[l,l+2^k-1\right]$，长度为 $2^k$。
其次，单点修改很简单，区间查询较为复杂。
所以，考虑使用相关数据结构和算法维护。
考虑 ST 表，这可以很好的维护长度为 $2^k$ 的区间信息。记 $\left[l,l+2^k-1\right]$ 的答案为 $\textit{st}_{l,k}$。在操作之前，使用普通 ST 表 $\mathcal O(n\log n)$ 预处理。
但是，ST 表是静态的，单点修改后重构的复杂度为 $\mathcal O(n)$。（并非 $\mathcal O(n\log n)$，设修改 $x$，则信息包含 $x$ 的点的区间 $[x-2^i+1,x]$ 需要满足 $i\leq\log n$，数量即 $\mathcal O(1+2+4+\cdots+n)=\mathcal O(n)$。）
因此，考虑复杂度均摊，考虑分治。设块长 $2^B$，并进行阈值分治。
单点修改重构后，处理 $\textit{st}_{x,k}$ 时，我们仅处理 $k\leq B$ 的情况，复杂度 $\mathcal O\left(2^B\right)$。
查询时，设 $\textit{query}(x,k)$ 表示答案。
-
若 $\textit{query}(x,k)$ 满足 $k\leq B$，则直接查询 $\textit{st}_{x,k}$。
-
否则有：
\[\textit{query}(x,k)=\vert\textit{query}(x,k-1)-\textit{query}(x+2^{k-1},k-1)\vert\]这样的复杂度是 $\mathcal O\left(\dfrac{n}{2^B}\right)$。
因为考虑到会递归 $k-B$ 层，即 $\mathcal O(\log n-B)$ 层。每一层都是双分支，复杂度即 $\mathcal O\left(2^{\log n-B}\right)=\mathcal O\left(\dfrac n{2^B}\right)$。
取 $B=\mathcal O\left(\dfrac{1}{2}\log n\right)$，可得最优复杂度。总复杂度为 $\mathcal O\left(n\log n+q\sqrt n\right)$。
AC 代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=200000;
int n,a[N+1],st[N+1][__lg(N+1)+1];
int B;
void stPre(){
for(int i=1;i<=n;i++){
st[i][0]=a[i];
}
for(int i=1;(1<<i)<=n;i++){
for(int x=1;x+(1<<i)-1<=n;x++){
st[x][i]=abs(st[x][i-1]-st[x+(1<<i-1)][i-1]);
}
}
}
void change(int p,int r){
st[p][0]=a[p]=r;
for(int i=1;i<=B;i++){
for(int x=max(p-(1<<i)+1,1);x<=p&&x+(1<<i)-1<=n;x++){
st[x][i]=abs(st[x][i-1]-st[x+(1<<i-1)][i-1]);
}
}
}
int query(int l,int k){
if(k<=B){
return st[l][k];
}else{
return abs(query(l,k-1)-query(l+(1<<k-1),k-1));
}
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
int q;
cin>>n>>q;
B=__lg(n)>>1;
for(int i=1;i<=n;i++){
cin>>a[i];
}
stPre();
while(q--){
int op,x,y;
cin>>op>>x>>y;
switch(op){
case 1:
change(x,y);
break;
case 2:
cout<<query(x,y)<<'\n';
break;
}
}
cout.flush();
fclose(stdin);
fclose(stdout);
return 0;
}
