这个线段树写起来还算简单 和之前的差不多
单点修改也很简单 用zkw直接改点就行了
#include <cstdio> #include <cstring> #include <algorithm> using namespace std; const int MAXN = 5e4 , INF =-0xffffff; struct stnode { int l,r,m,s; void init(int v=INF) { l=r=m=s=v; } }; inline int max(int a,int b,int c) { return max(a,max(b,c)); } struct zKWSegmentTree { stnode st[MAXN<<4]; int sz; void init(int n) { int i,t,end; for(sz=1,end=n+2;sz<end;sz<<=1); st[sz].init(); for(i=sz+1,end=sz+n+1;i<end;i++) { scanf("%d",&t); st[i].init(t); } for(end=sz<<1;i<end;i++) st[i].init(); for(i=sz-1;i>0;i--) { int l=i<<1,r=l+1; st[i].s=st[l].s+st[r].s; st[i].l=max(st[l].l,st[l].s+st[r].l); st[i].r=max(st[r].r,st[r].s+st[l].r); st[i].m=max(st[l].m,st[r].m,st[l].r+st[r].l); //printf("[%d]:%d %d %d\n",i,st[i].l,st[i].r,st[i].m); } } void change(int pos,int v) { pos+=sz; st[pos].init(v); for(int i=pos>>=1;i>0;i>>=1) { int l=i<<1,r=l+1; st[i].s=st[l].s+st[r].s; st[i].l=max(st[l].l,st[l].s+st[r].l); st[i].r=max(st[r].r,st[r].s+st[l].r); st[i].m=max(st[l].m,st[r].m,st[l].r+st[r].l); } } int quire(int l,int r) { int lsum,rsum,msum; lsum=rsum=msum=INF; for(l+=sz-1,r+=sz+1;l^r^1;l>>=1,r>>=1) { if(~l&1) { msum=max(st[l^1].m,lsum+st[l^1].l,msum); lsum=max(st[l^1].r,lsum+st[l^1].s); } if(r&1) { msum=max(st[r^1].m,rsum+st[r^1].r,msum); rsum=max(st[r^1].l,rsum+st[r^1].s); } //printf("%d to %d\t%d %d %d\n",l,r,lsum,rsum,msum); } return max(max(lsum,rsum,msum),lsum+rsum); } }st; int main() { int n; scanf("%d",&n); st.init(n); scanf("%d",&n); while(n--) { int op,a,b; scanf("%d%d%d",&op,&a,&b); if(op) { printf("%d\n",st.quire(a,b)); } else st.change(a,b); } return 0; }
/********和题目关联不大分割线
1.GSS2难度有点大 驾驭不来..
2.话说如果建树的时候把用一个数组指针 都指向叶节点的值单点修改也是很快的
想到这里 我又想了想zkw和普通线段树的区别
zkw是完全二叉树 这样left 和 right 找到共同祖先就只要经过相同数量 找爸爸 操作就能找到LCA了