题意：给定N个K维的点，Q次操作，或者修改点的坐标；或者问[L,R]这些点中最远的点。
思路：因为最后一定可以表示维+/-(x1-x2)+/-(y1-y2)+/-(z1-z2).....
所以我们可以保存到线段树里，每次求区间最大值和最小值即可。
注意到我们可以先确定一个点的正负号，所以时间和空间节省了一半。
#include<bits/stdc++.h>
#define mp make_pair
#define pii pair<int,int>
#define F first
#define S second
#define lson Now<<1
#define rson Now<<1|1
#define rep(i,a,b) for(int i=a;i<=b;i++)
using namespace std;
const int maxn=;
const int inf=;
struct T
{
int Mx[maxn],Mn[maxn];
void update(int Now,int L,int R,int pos,int val)
{
if(L==R){ Mn[Now]=Mx[Now]=val; return ;}
int Mid=(L+R)>>;
if(pos<=Mid) update(lson,L,Mid,pos,val);
else update(rson,Mid+,R,pos,val);
Mx[Now]=max(Mx[lson],Mx[rson]); Mn[Now]=min(Mn[lson],Mn[rson]);
}
pii query(int Now,int L,int R,int l,int r)
{
if(l<=L&&r>=R) return mp(Mx[Now],Mn[Now]);
int Mid=(L+R)>>; int mx=-inf,mn=inf; pii tmp;
if(l<=Mid){
tmp=query(lson,L,Mid,l,r);
mx=max(mx,tmp.F); mn=min(mn,tmp.S);
}
if(r>Mid){
tmp=query(rson,Mid+,R,l,r);
mx=max(mx,tmp.F); mn=min(mn,tmp.S);
}
return mp(mx,mn);
}
}t[];
int main()
{
int N,K,M,opt,L,R,p,x[],KK;
scanf("%d%d",&N,&K); KK=(<<(K-))-;
rep(i,,KK){
rep(j,,N*) t[i].Mn[j]=inf,t[i].Mx[j]=-inf;
}
rep(i,,N){
rep(j,,K-) scanf("%d",&x[j]);
rep(j,,KK) {
int tmp=;
rep(k,,K-) if(j&(<<k)) tmp+=x[k];else tmp-=x[k];
t[j].update(,,N,i,tmp);
}
}
scanf("%d",&M);
rep(i,,M){
scanf("%d",&opt);
if(opt==){
scanf("%d%d",&L,&R);
int ans=-inf; pii tmp;
rep(j,,KK){
pii tmp=t[j].query(,,N,L,R);
ans=max(ans,tmp.F-tmp.S);
ans=max(ans,tmp.S-tmp.F);
}
printf("%d\n",ans);
}
else {
scanf("%d",&p); rep(j,,K-) scanf("%d",&x[j]);
rep(j,,KK) {
int tmp=;
rep(k,,K-) if(j&(<<k)) tmp+=x[k];else tmp-=x[k];
t[j].update(,,N,p,tmp);
}
}
}
return ;
}