建树
void build(int o,int l,int r) //o:当前建立的节点 l:左端点 r:右端点 { if(l == r) //建立叶子信息 st[o] = a[l]; else { int m = l + ((r-l) >> 1); // m 为中间点，左儿子结点为 [l,m] ，右儿子结点为 [m+1,r]； build(o << 1,l,m); //构建左儿子结点 build((o<<1)|1,m+1,r); //构建右儿子结点 st[o] = max(st[o << 1],st[(o<<1)|1]); //递归返回时用儿子结点更新父节点，此处可进行更新最大值、最小值、区间和等操作 } } build(1, 1, n);//主函数里的语句
单点修改
void update(int o,int l,int r,int ind,int ans) //o、l、r为当前更新到的结点、左右端点，ind为需要修改的叶子结点左端点，ans为需要修改成的值； { if(l == r) //若当前更新点的左右端点相等即到叶子结点时，直接更新信息并返回 { st[o] = ans; return ; } int m = l + ((r-l) >> 1); if(ind <= m) update(o << 1,l,m,ind,ans); else update((o<<1)|1,m+1,r,ind,ans); st[o] = max(st[o<<1],st[(o<<1)|1]); //递归回之后用儿子结点更新父节点（此处是区间最大值）也可以是最小值或者是区间和 } update(1, 1, n, a, b);//在主函数里的语句
区间查询
int query(int o,int l,int r,int ql,int qr) //ql、qr为需要查询的区间左右端点 { if(ql > r || qr < l) //若当前结点和需要查找的区间不相交，则返回一个对于区间查询无关的值（如求和时返回0，求最大值时返回-1等） return -1; if(ql <=l && qr >=r) //若当前结点的区间被需要查询的区间覆盖，则返回当前结点的信息 return st[o]; int m = l + ((r-l) >> 1); int p1 = query(o<<1,l,m,ql,qr); //p1为查询左儿子结点得到的信息，p2为查询右儿子结点得到的信息 int p2 = query((o<<1)|1,m+1,r,ql,qr); return max(p1,p2); //综合两个儿子结点的信息并返回 } query(1, 1, n, a, b)//主函数里的查询语句
然后是线段数的区间修改以及相应的查询：
区间修改用到了lazy的思想，即当一个区间需要更新时，只递归更新到那一层结点，并将其下层结点所需要更新的信息保存在数组中，然后返回，只有当下次遍历到那个结点（更新过程中或查询过程中），才将那个结点的修改信息传递下去，这样就避免了区间修改的每个值的修改
区间修改（包括区间加值和区间赋值）及相应查询：
区间加值：
void pushup(int o){ //pushup函数，该函数本身是将当前结点用左右子节点的信息更新，此处求区间和，用于update中将结点信息传递完返回后更新父节点 st[o]=st[o<<1]+st[o<<1|1]; } void pushdown(int o,int l,int r){ //pushdown函数，将o结点的信息传递到左右子节点上 if(add[o]){ //当父节点有更新信息时才向下传递信息 add[o<<1]+=add[o]; //左右儿子结点均加上父节点的更新值 add[o<<1|1]+=add[o]; int m=l+((r-l)>>1); st[o<<1]+=add[o]*(m-l+1); //左右儿子结点均按照需要加的值总和更新结点信息 st[o<<1|1]+=add[o]*(r-m); add[o]=0; //信息传递完之后就可以将父节点的更新信息删除 } } void update(int o,int l,int r,int ql,int qr,int addv){ //ql、qr为需要更新的区间左右端点，addv为需要增加的值 if(ql<=l&&qr>=r){ //与单点更新一样，当当前结点被需要更新的区间覆盖时 add[o]+=addv; //更新该结点的所需更新信息 st[o]+=addv*(r-l+1); //更新该结点信息 return; //根据lazy思想，由于不需要遍历到下层结点，因此不需要继续向下更新，直接返回 } pushdown(o,l,r); //将当前结点的所需更新信息传递到下一层（其左右儿子结点） int m=l+((r-l)>>1); if(ql<=m)update(o<<1,l,m,ql,qr,addv); //当需更新区间在当前结点的左儿子结点内，则更新左儿子结点 if(qr>=m+1)update(o<<1|1,m+1,r,ql,qr,addv); //当需更新区间在当前结点的右儿子结点内，则更新右儿子结点 pushup(o); //递归回上层时一步一步更新回父节点 } ll query(int o,int l,int r,int ql,int qr){ //ql、qr为需要查询的区间 if(ql<=l&&qr>=r) return st[o]; //若当前结点覆盖区间即为需要查询的区间，则直接返回当前结点的信息 pushdown(o,l,r); //将当前结点的更新信息传递给其左右子节点 int m=l+((r-l)>>1); ll ans=0; //所需查询的结果 if(ql<=m)ans+=query(o<<1,l,m,ql,qr); //若所需查询的区间与当前结点的左子节点有交集，则结果加上查询其左子节点的结果 if(qr>=m+1)ans+=query(o<<1|1,m+1,r,ql,qr); //若所需查询的区间与当前结点的右子节点有交集，则结果加上查询其右子节点的结果 return ans; }
区间改值（其实只有pushdown函数和update中修改部分与区间加值不同）：
void pushup(int o){ st[o]=st[o<<1]+st[o<<1|1]; } void pushdown(int o,int l,int r){ //pushdown和区间加值不同，改值时修改结点信息只需要对修改后的信息求和即可，不用加上原信息 if(change[o]){ int c=change[o]; change[o<<1]=c; change[o<<1|1]=c; int m=l+((r-l)>>1); st[o<<1]=(m-l+1)*c; st[o<<1|1]=(r-m)*c; change[o]=0; } } void update(int o,int l,int r,int ql,int qr,int c){ if(ql<=l&&qr>=r){ //同样更新结点信息和区间加值不同 change[o]=c; st[o]=(r-l+1)*c; return; } pushdown(o,l,r); int m=l+((r-l)>>1); if(ql<=m)update(o<<1,l,m,ql,qr,c); if(qr>=m+1)update(o<<1|1,m+1,r,ql,qr,c); pushup(o); } int query(int o,int l,int r,int ql,int qr){ if(ql<=l&&qr>=r) return st[o]; pushdown(o,l,r); int m=l+((r-l)>>1); int ans=0; if(ql<=m)ans+=query(o<<1,l,m,ql,qr); if(qr>=m+1)ans+=query(o<<1|1,m+1,r,ql,qr); return ans; }
最大子段和板子
/* s的维护很常规， ls：有两种情况： 1.该区间内的ls是ta左儿子的ls 2.该区间内的ls是左儿子的s+右儿子的ls 同理，rs：有两种情况： 1.该区间内的rs是ta右儿子的rs 2.该区间内的rs是右儿子的s+左儿子的rs 而ms有三种情况： 1.该区间内的ms是左儿子的ms 2.该区间内的ms是右儿子的ms 3.该区间内的ms是左儿子的rs+右儿子的ls */ #include<cstdio> #include<cstring> #include<iostream> using namespace std; const int N=100001; int n; int l,r; int a[N]; struct node{ int x,y,ls,rs,s,ms; //ls 紧靠左边的最大子段和 rs 紧靠右边的最大子段和 }; node tree[N<<2]; void update(int bh) { tree[bh].ms=max(tree[bh<<1].ms,tree[(bh<<1)+1].ms); tree[bh].ms=max(tree[bh].ms,tree[bh<<1].rs+tree[(bh<<1)+1].ls); tree[bh].ls=max(tree[bh<<1].ls,tree[bh<<1].s+tree[(bh<<1)+1].ls); tree[bh].rs=max(tree[(bh<<1)+1].rs,tree[(bh<<1)+1].s+tree[bh<<1].rs); tree[bh].s=tree[bh<<1].s+tree[(bh<<1)+1].s; return; } void build(int bh,int l,int r) { tree[bh].x=l; tree[bh].y=r; if (l==r) { tree[bh].s=tree[bh].ms=tree[bh].ls=tree[bh].rs=a[l]; return; } int mid=(l+r)>>1; build(bh<<1,l,mid); build((bh<<1)+1,mid+1,r); update(bh); } void change(int bh,int mb,int z) //单点修改 { if (tree[bh].x==tree[bh].y&&tree[bh].x==mb) { tree[bh].s=tree[bh].ms=tree[bh].ls=tree[bh].rs=z; return; } int mid=(tree[bh].x+tree[bh].y)>>1; if (mb<=mid) change(bh<<1,mb,z); else change((bh<<1)+1,mb,z); update(bh); } int askl(int bh,int l,int r) //在[l,r]中查找紧靠左端的最大子段和 { if (tree[bh].x==l&&tree[bh].y==r) return tree[bh].ls; int mid=(tree[bh].x+tree[bh].y)>>1; if (r<=mid) askl(bh<<1,l,r); else if (l>mid) askl((bh<<1)+1,l,r); int lans=(bh<<1,l,mid); //左儿子中紧靠左的最大子段和 int rans=((bh<<1)+1,mid+1,r); //右儿子中紧靠左的最大子段和 return max(lans,rans+tree[bh<<1].s); //rans+tree[bh<<1].s } int askr(int bh,int l,int r) //在[l,r]中查找紧靠右端的最大子段和 { if (tree[bh].x==l&&tree[bh].y==r) return tree[bh].rs; int mid=(tree[bh].x+tree[bh].y)>>1; if (r<=mid) askr(bh<<1,l,r); else if (l>mid) askr((bh<<1)+1,l,r); int lans=askr(bh<<1,l,mid); //左儿子中紧靠右的最大子段和 int rans=askr((bh<<1)+1,mid+1,r); //右儿子中紧靠右的最大子段和 return max(rans,lans+tree[(bh<<1)+1].s); } int ask(int bh,int l,int r) //ask是专用来考虑[l,r]的最大子段和独立的存在于左子段中， { //或右子段中，没有跨段的情况 if (tree[bh].x==l&&tree[bh].y==r) return tree[bh].ms; int mid=(tree[bh].x+tree[bh].y)>>1; //// if (r<=mid) ask(bh<<1,l,r); else if (l>mid) ask((bh<<1)+1,l,r); int lans=ask(bh<<1,l,mid); int rans=ask((bh<<1)+1,mid+1,r); int ans=max(lans,rans); return max(ans,askr(bh<<1,l,mid)+askl((bh<<1)+1,mid+1,r)); } //askr(bh<<1,l,mid)+askl((bh<<1)+1,mid+1,r) 这是将[l,r]劈成两段，最大子段在两部分中都有一部分 //需要注意的是，在分成两段分别求解时，[l,r]的范围会改变 int main() { scanf("%d",&n); for (int i=1;i<=n;i++) scanf("%d",&a[i]); build(1,1,n); int T; scanf("%d",&T); while (T--) { int x,y; scanf("%d%d",&x,&y); printf("%d",ask(1,x,y)); } return 0; }
最大子段和 hdu6638
#include<iostream> #include<cstdio> #include<cstdlib> #include<cstring> #include<algorithm> #include<cmath> #include<queue> #include<list> #include<math.h> #include<vector> #include<stack> #include<string> #include<stdio.h> using namespace std; typedef long long LL; const int MAXN = 2e3 + 10; const int maxn=5e4 + 10; struct T{ LL x,y,w; T(){} T(LL x,LL y,LL w) : x(x),y(y),w(w){} }a[MAXN]; struct Segtree{ int l,r; LL lx,rx,mx,sum; }st[MAXN << 2]; bool cmp(T a,T b) { return a.x < b.x; } LL b[MAXN]; void pushup(int o) { st[o].sum = st[o << 1].sum + st[o << 1 | 1].sum; st[o].lx = max(st[o << 1].lx,st[o << 1].sum + st[o << 1 | 1].lx); st[o].rx = max(st[o << 1 | 1].rx,st[o << 1 | 1].sum + st[o << 1].rx); st[o].mx = max(max(st[o << 1].mx,st[o << 1 | 1].mx),st[o << 1].rx + st[o << 1 | 1].lx); } void build(int o,int l,int r) { st[o].l = l; st[o].r = r; st[o].sum = st[o].mx = st[o].lx = st[o].rx = 0; if(l == r) { return; } int m = (l + r) >> 1; build(o << 1, l, m); build(o << 1 | 1, m + 1, r); } void insert(int o,int x,int w) { if(st[o].l == st[o].r) { st[o].sum = st[o].lx = st[o].rx = st[o].mx = st[o].mx + w; return; } int m = (st[o].l + st[o].r) >> 1; if(x <= m) insert(o << 1,x,w); else insert(o << 1 | 1,x,w); pushup(o); } int main() { int t; scanf("%d",&t); while(t--) { int n; scanf("%d",&n); for(int i = 1; i <= n; i++) { LL x,y,w; scanf("%lld %lld %lld",&x,&y,&w); a[i] = T(x,y,w); b[i] = y; } sort(b + 1,b + n + 1); int k = unique(b + 1,b + n + 1) - b - 1; for(int i = 1; i <= n; i++) { int y = lower_bound(b + 1,b + k + 1,a[i].y) - b; a[i].y = y; } sort(a + 1,a + n + 1,cmp); LL ans = 0; for(int i = 1; i <= n; i++) { if(i != 1 && a[i].x == a[i - 1].x) continue; build(1,1,k); for(int j = i; j <= n; j++) { if(j != i && a[j].x != a[j - 1].x) ans = max(ans,st[1].mx); insert(1,a[j].y,a[j].w); } ans = max(ans,st[1].mx); } cout << ans << endl; } }