设置一个值K。
d<=K：建立多组线段树；d>K：暴力。
最优时间复杂度的伪计算：
O(n*K*logn(建树)+m*logn(询问类型1)+m*n/K(询问类型2)+m*K*logn(修改))。
求此函数最小值，易得，当K=sqrt(m/logn)时，
时间复杂度：O(m*sqrt(m*logn))。
空间复杂度：O(n*sqrt(m/logn))。
当然，这个计算显然不完全合理，而且，由于使用STL的vector的原因，导致实际建树要慢得多，因此K取得小一些更加合适(跑几组数据自己看看就行了)。如果不稍微小一点是卡不进内存和时间的哦。
#include<cstdio>
#include<vector>
#include<cmath>
using namespace std;
#define lson rt<<1,l,m
#define rson rt<<1|1,m+1,r
#define INF 2147483647
int n,x0,d,a[70001],lim,m;
bool op;
vector<int>b[70][70],maxv[70][70];
void buildtree(int x,int y,int rt,int l,int r)
{
if(l==r)
{
maxv[x][y][rt]=b[x][y][l];
return;
}
int m=l+r>>1;
buildtree(x,y,lson); buildtree(x,y,rson);
maxv[x][y][rt]=max(maxv[x][y][rt<<1],maxv[x][y][rt<<1|1]);
}
void update(int x,int y,int p,int v,int rt,int l,int r)
{
if(l==r) {maxv[x][y][rt]+=v; return;}
int m=l+r>>1;
if(p<=m) update(x,y,p,v,lson);
else update(x,y,p,v,rson);
maxv[x][y][rt]=max(maxv[x][y][rt<<1],maxv[x][y][rt<<1|1]);
}
int query(int x,int y,int ql,int qr,int rt,int l,int r)
{
if(ql<=l&&r<=qr) return maxv[x][y][rt];
int m=l+r>>1,res=-INF;
if(ql<=m) res=max(res,query(x,y,ql,qr,lson));
if(m<qr) res=max(res,query(x,y,ql,qr,rson));
return res;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;++i) scanf("%d",&a[i]);
scanf("%d",&m);
lim=(int)sqrt((double)m/(log((double)n)/log(2.0)))/14;
if(!lim) lim=1;
for(int i=1;i<=lim;++i)//枚举公差
for(int j=1;j<=lim;++j)//枚举首项
{
b[i][j].push_back(0);
for(int k=j;k<=n;k+=i) b[i][j].push_back(a[k]);
maxv[i][j].assign((b[i][j].size()-1)<<2|1,0);
buildtree(i,j,1,1,b[i][j].size()-1);
}
for(int i=1;i<=m;++i)
{
scanf("%d%d%d",&op,&x0,&d);
if(!op)
{
a[x0]+=d;
for(int j=1;j<=lim;++j)//枚举公差
{
int bel=x0%j;
if(!bel) bel=j;//计算首项
int pos=x0/j;
if(bel!=j) ++pos;//计算pos是该等差数列的第几项
update(j,bel,pos,d,1,1,b[j][bel].size()-1);
}
}
else
{
if(d>lim)
{
int res=-INF;
for(int j=x0;j<=n;j+=d) res=max(res,a[j]);
printf("%d
",res);
}
else
{
int bel=x0%d;
if(!bel) bel=d;
int sta=x0/d;
if(bel!=d) ++sta;
printf("%d
",query(d,bel,sta,b[d][bel].size()-1,1,1,b[d][bel].size()-1));
}
}
}
return 0;
}