https://www.spoj.com/problems/GSS1/
https://cp-algorithms.com/data_structures/segment_tree.html
https://blog.csdn.net/weixin_40894017/article/details/82890473
这种类似于分治的思想我一直不能很好的掌握。。。
题目大意就是给你一段序列每次查需(l,r)内最大的连续区间和。
对于一个区间的最大连续和它可能出现的位置，前缀 后缀 或者从中间向两边拓展
所以对于每一个节点我们维护他的
ls：从左端点开始的最大连续和
rs 以右端点结束的最大连续和
ms：整个区间的最大连续和
s：区间和。
至于为什么要维护一个区间和,其实也是为了转移方便。
对于一个父节点它的ls 能够更新位左子区间的和加上右子区间的ls。
下面说明如何合并两个区间。
ls ：max （lson.ls,lson.s+rson.ls）;
rs :max(rson.rs,rson.s+lson.rs);
ms:max( max(lson.ms,rson.ms),lson.rs+rson.ls);//这里是因为最大连续和可能出现在从中间到两边拓展的情况。
以上是合并两个区间。。
下面是如何查询。
如何合并区间容易想到。。可能我对于递归还不是太了解，解决了区间合并却不知道要如何去查询。
对于我们要查询的区间我们可以把它分为2种情况。
当前节点完全等于查询的区间，查询的区间位当前节点的子区间。
这样对一个查询区间，我们就可以在线段树上找到若干个完整的区间，。。
比如当前的序列长度是1-7
如图所示：如果我们查询2-6
我们就可以在树上找到2 3-4 5-6
同样的当我们找到2 3-4 这样两个相邻区间时我们也要像建树时那样合并两个区间成位一个新的区间。。。
struct node
{
int ls,rs,s,ms;
}t[N*4];
int a[N];
void pushup(int rt)
{
t[rt].ls=max(t[rt<<1].ls,t[rt<<1].s+t[rt<<1|1].ls);
t[rt].rs=max(t[rt<<1|1].rs,t[rt<<1|1].s+t[rt<<1].rs);
t[rt].ms=max(t[rt<<1].ms,t[rt<<1|1].ms);
t[rt].ms=max(t[rt].ms,t[rt<<1].rs+t[rt<<1|1].ls);
t[rt].s=t[rt<<1].s+t[rt<<1|1].s;
return ;
}
void build(int rt,int l,int r)
{
if(l==r)
{
t[rt].ls=a[l];
t[rt].rs=a[l];
t[rt].ms=a[l];
t[rt].s =a[l];
return ;
}
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
pushup(rt);
}
node query(int rt,int l,int r,int ql,int qr)
{
if(l==ql && r==qr)
{
return t[rt];
}
int m=(l+r)>>1;
if(m>=qr)return query(rt<<1,l,m,ql,qr);
if(m<ql) return query(rt<<1|1,m+1,r,ql,qr);
else
{
node lans=query(rt<<1,l,m,ql,m);
node rans=query(rt<<1|1,m+1,r,m+1,qr);
node ans;
ans.ls=max(lans.ls,lans.s+rans.ls);
ans.rs=max(rans.rs,rans.s+lans.rs);
ans.ms=max(lans.ms,rans.ms);
ans.ms=max(ans.ms,lans.rs+rans.ls);
ans.s=lans.s+rans.s;
return ans;
}
https://www.cnblogs.com/qixingzhi/p/9435540.html
https://blog.csdn.net/honeyaya/article/details/11536695
区间合并，经常询问区间中满足条件的连续最长区间
由于没有涉及到更新操作，只是在询问，故可以把这棵树做成静态的，
对于一段区间 [a,b] 的最大子段和，我们把这个区间分开来开，[a,m] ,[ m+1,b],那么最大子段和或出现在[a,m], or [m+1,b] or 穿插这两个区间~~~~
重点处理穿插的情况：
那必然是[a,m]的最大的右边的那个序列得和 + [m+1,b] 最左边的那个和，，因为子段和一定是连续的，从而加入了每个节点的两个属性
https://blog.csdn.net/dgghjnjk/article/details/52452735
http://www.cnblogs.com/ckxkexing/p/9636804.html
GSS3 - Can you answer these queries III
You are given a sequence A[1], A[2], ..., A[N] . ( |A[i]| ≤ 15007 , 1 ≤ N ≤ 50000 ). A query is defined as follows:
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.
Query(x,y) = Max { a[i]+a[i+1]+...+a[j] ; x ≤ i ≤ j ≤ y }.
Given M queries, your program must output the results of these queries.
Input
- The first line of the input file contains the integer N.
- In the second line, N numbers follow.
- The third line contains the integer M.
- M lines follow, where line i contains 2 numbers xi and yi.
Output
Your program should output the results of the M queries, one query per line.
Example
Input: 3 -1 2 3 1 1 2 Output: 2
Finding subsegments with the maximal sum
Here again we receive a range for each query, this time we have to find a subsegment such that and and the sum of the elements of this segment is maximal. As before we also want to be able to modify individual elements of the array. The elements of the array can be negative, and the optimal subsegment can be empty (e.g. if all elements are negative).
This problem is a non-trivial usage of a Segment Tree. This time we will store four values for each vertex: the sum of the segment, the maximum prefix sum, the maximum suffix sum, and the sum of the maximal subsegment in it. In other words for each segment of the Segment Tree the answer is already precomputed as well as the answers for segments touching the left and the right boundaries of the segment.
How to build a tree with such data? Again we compute it in a recursive fashion: we first compute all four values for the left and the right child, and then combine those to archive the four values for the current vertex. Note the answer for the current vertex is either:
- the answer of the left child, which means that the optimal subsegment is entirely placed in the segment of the left child
- the answer of the right child, which means that the optimal subsegment is entirely placed in the segment of the right child
- the sum of the maximum suffix sum of the left child and the maximum prefix sum of the right child, which means that the optimal subsegment intersects with both children.
Hence the answer to the current vertex is the maximum of these three values. Computing the maximum prefix / suffix sum is even easier. Here is the implementation of the function, which receives only data from the left and right child, and returns the data of the current vertex.
struct data {
int sum, pref, suff, ans;
};
data combine(data l, data r) {
data res;
res.sum = l.sum + r.sum;
res.pref = max(l.pref, l.sum + r.pref);
res.suff = max(r.suff, r.sum + l.suff);
res.ans = max(max(l.ans, r.ans), l.suff + r.pref);
return res;
}
Using the function it is easy to build the Segment Tree. We can implement it in exactly the same way as in the previous implementations. To initialize the leaf vertices, we additionally create the auxiliary function , which will return a object holding the information of a single value.
data make_data(int val) {
data res;
res.sum = val;
res.pref = res.suff = res.ans = max(0, val);
return res;
}
void build(int a[], int v, int tl, int tr) {
if (tl == tr) {
t[v] = make_data(a[tl]);
} else {
int tm = (tl + tr) / 2;
build(a, v*2, tl, tm);
build(a, v*2+1, tm+1, tr);
t[v] = combine(t[v*2], t[v*2+1]);
}
}
void update(int v, int tl, int tr, int pos, int new_val) {
if (tl == tr) {
t[v] = make_data(new_val);
} else {
int tm = (tl + tr) / 2;
if (pos <= tm)
update(v*2, tl, tm, pos, new_val);
else
update(v*2+1, tm+1, tr, pos, new_val);
t[v] = combine(t[v*2], t[v*2+1]);
}
}
It only remains, how to compute the answer to a query. To answer it, we go down the tree as before, breaking the query into several subsegments that coincide with the segments of the Segment Tree, and combine the answers in them into a single answer for the query. Then it should be clear, that the work is exactly the same as in the simple Segment Tree, but instead of summing / minimizing / maximizing the values, we use the function.
data query(int v, int tl, int tr, int l, int r) {
if (l > r)
return make_data(0);
if (l == tl && r == tr)
return t[v];
int tm = (tl + tr) / 2;
return combine(query(v*2, tl, tm, l, min(r, tm)),
query(v*2+1, tm+1, tr, max(l, tm+1), r));
}
As it turns out, we need to store 4 values in each segment tree node to be able to merge child nodes to form a solution to their parent’s node:
- Maximum sum of a subarray, starting at the leftmost index of this range
- Maximum sum of a subarray, ending at the rightmost index of this range
- Maximum sum of any subarray in this range
- Sum of all elements in this range
https://blog.csdn.net/weixin_40894017/article/details/82890473
这种类似于分治的思想我一直不能很好的掌握。。。
题目大意就是给你一段序列每次查需(l,r)内最大的连续区间和。
对于一个区间的最大连续和它可能出现的位置，前缀 后缀 或者从中间向两边拓展
所以对于每一个节点我们维护他的
ls：从左端点开始的最大连续和
rs 以右端点结束的最大连续和
ms：整个区间的最大连续和
s：区间和。
至于为什么要维护一个区间和,其实也是为了转移方便。
对于一个父节点它的ls 能够更新位左子区间的和加上右子区间的ls。
下面说明如何合并两个区间。
ls ：max （lson.ls,lson.s+rson.ls）;
rs :max(rson.rs,rson.s+lson.rs);
ms:max( max(lson.ms,rson.ms),lson.rs+rson.ls);//这里是因为最大连续和可能出现在从中间到两边拓展的情况。
以上是合并两个区间。。
下面是如何查询。
如何合并区间容易想到。。可能我对于递归还不是太了解，解决了区间合并却不知道要如何去查询。
对于我们要查询的区间我们可以把它分为2种情况。
当前节点完全等于查询的区间，查询的区间位当前节点的子区间。
这样对一个查询区间，我们就可以在线段树上找到若干个完整的区间，。。
比如当前的序列长度是1-7
如图所示：如果我们查询2-6
我们就可以在树上找到2 3-4 5-6
同样的当我们找到2 3-4 这样两个相邻区间时我们也要像建树时那样合并两个区间成位一个新的区间。。。
struct node
{
int ls,rs,s,ms;
}t[N*4];
int a[N];
void pushup(int rt)
{
t[rt].ls=max(t[rt<<1].ls,t[rt<<1].s+t[rt<<1|1].ls);
t[rt].rs=max(t[rt<<1|1].rs,t[rt<<1|1].s+t[rt<<1].rs);
t[rt].ms=max(t[rt<<1].ms,t[rt<<1|1].ms);
t[rt].ms=max(t[rt].ms,t[rt<<1].rs+t[rt<<1|1].ls);
t[rt].s=t[rt<<1].s+t[rt<<1|1].s;
return ;
}
void build(int rt,int l,int r)
{
if(l==r)
{
t[rt].ls=a[l];
t[rt].rs=a[l];
t[rt].ms=a[l];
t[rt].s =a[l];
return ;
}
int m=(l+r)>>1;
build(rt<<1,l,m);
build(rt<<1|1,m+1,r);
pushup(rt);
}
node query(int rt,int l,int r,int ql,int qr)
{
if(l==ql && r==qr)
{
return t[rt];
}
int m=(l+r)>>1;
if(m>=qr)return query(rt<<1,l,m,ql,qr);
if(m<ql) return query(rt<<1|1,m+1,r,ql,qr);
else
{
node lans=query(rt<<1,l,m,ql,m);
node rans=query(rt<<1|1,m+1,r,m+1,qr);
node ans;
ans.ls=max(lans.ls,lans.s+rans.ls);
ans.rs=max(rans.rs,rans.s+lans.rs);
ans.ms=max(lans.ms,rans.ms);
ans.ms=max(ans.ms,lans.rs+rans.ls);
ans.s=lans.s+rans.s;
return ans;
}
https://www.cnblogs.com/qixingzhi/p/9435540.html
我们可以考虑，如果一组数据全部都是正数，那么问题等同于是查询区间和。然而如果有负数的存在，问题就不一样了
考虑对于每一个节点，维护四个信息：ls（代表当前区间一定顶着左端点的最大子段和），rs（同理，一定顶着右端点的），sum（区间和），val（最大子段和，也就是答案）
考虑进行转移——一个节点的信息由它的两个子节点转移而来
。子段和之所以不包括整段区间是由于右端有负数。因此再往右扩展不会更优
rs同理转移。sum就不说了
. 最难理解的是最后一部分。
想象一下，当前区间的最大子段和要么有一头顶住端点，要么两头都不碰到端点。
对于有一头一定碰到的情况，直接用转移即可。（注意，这里所说的是一定碰到，当然最大子段也有可能碰到，但是不一定）
对于都不碰到的情况，如果其不跨过中间，那么分别用两个子节点的val转移。如果恰好跨过中间，那我们需要把它拼接起来——为了使答案最优，我们考虑拼接 （仔细思考）
查询的时候也一样，还是通过递归来完成转移。这里需要对线段树的query有一个较为深刻的理解——不同于build，query(l,r)表示的是区间中包含在查询区间的那一部分，而不是真的。因为在递归的时候我们会判断超界。另外，这里的转移需要刚才的四个参数，因此query的返回值应当是一个结构体，而不是单单一个数值。我暂时还没有想出非结构体的做法……
int ls[MAXN<<2], rs[MAXN<<2], sum[MAXN<<2], val[MAXN<<2]; inline void Pushup(int rt){ sum[rt] = sum[rt<<1] + sum[rt<<1|1]; ls[rt] = Max(ls[rt<<1], sum[rt<<1]+ls[rt<<1|1]); rs[rt] = Max(rs[rt<<1|1], sum[rt<<1|1]+rs[rt<<1]); val[rt] = Max(Max(val[rt<<1], val[rt<<1|1]), Max(Max(ls[rt], rs[rt]), rs[rt<<1] + ls[rt<<1|1])); } void build(int L, int R, int rt){ if(L >= R){ val[rt] = sum[rt] = ls[rt] = rs[rt] = a[L]; return; } int Mid = (L + R) >> 1; build(L, Mid, rt<<1); build(Mid+1, R, rt<<1|1); Pushup(rt); } Data query(int L, int R, int rt, int x, int y){ if(x<=L && R<=y) return (Data){ls[rt],rs[rt],sum[rt],val[rt]}; int Mid = (L + R) >> 1; if(y <= Mid) return query(L, Mid, rt<<1, x, y); if(x >= Mid+1) return query(Mid+1, R, rt<<1|1, x, y); Data res, t_1 = query(L, Mid, rt<<1, x, y), t_2 = query(Mid+1, R, rt<<1|1, x, y); res.sum = t_1.sum + t_2.sum; res.ls = Max(t_1.ls, t_1.sum + t_2.ls); res.rs = Max(t_2.rs, t_1.rs + t_2.sum); res.val = Max(Max(t_1.val, t_2.val), Max(Max(res.ls, res.rs), t_1.rs + t_2.ls)); return res; }
https://blog.csdn.net/honeyaya/article/details/11536695
区间合并，经常询问区间中满足条件的连续最长区间
由于没有涉及到更新操作，只是在询问，故可以把这棵树做成静态的，
对于一段区间 [a,b] 的最大子段和，我们把这个区间分开来开，[a,m] ,[ m+1,b],那么最大子段和或出现在[a,m], or [m+1,b] or 穿插这两个区间~~~~
重点处理穿插的情况：
那必然是[a,m]的最大的右边的那个序列得和 + [m+1,b] 最左边的那个和，，因为子段和一定是连续的，从而加入了每个节点的两个属性
https://blog.csdn.net/dgghjnjk/article/details/52452735
这个题目可以用线段树去做，一个可行的思路就是计算出三个标记mc[]（当前区间内最大的连续子串和），lc[]（从当前区间左端点开始向右的最大的连续子串和），rc[]（从当前区间右端点开始的向左的最大的连续子串和）。
查询的时候利用这三个标记进行计算就可以了。
线段树，每个线段树的节点要维护对应区间的最大值ans，与左端点相连的最大值lv，与右端点相连的最大值rv，还有区间全部的总和V；
每个区间的lv 就是 （左子区间的lv ，左子区间v + 右子区间的lv） 中的较大者。rv同理。
每个区间的ans就是，（左子区间的ans，右子区间的ans， 左子区间和右子区间中间连接的那段）中的较大者。
const int maxn = 50009; int a[maxn]; struct node { int lv,rv,v; int ans; node(){ lv = rv = v = ans = -inf; } }p[maxn<<2]; void pushup(int rt){ p[rt].v = p[rt<<1].v + p[rt<<1|1].v; p[rt].lv = max(p[rt<<1].lv, p[rt<<1].v + p[rt<<1|1].lv); p[rt].rv = max(p[rt<<1|1].rv, p[rt<<1|1].v + p[rt<<1].rv); p[rt].ans = max3(p[rt<<1].ans, p[rt<<1|1].ans, p[rt<<1].rv + p[rt<<1|1].lv); } void build(int l,int r,int rt){ if(l==r){ p[rt].v = p[rt].lv = p[rt].rv = p[rt].ans = a[l]; return; } int mid = (l + r)>>1; build(l,mid,rt<<1); build(mid+1,r,rt<<1|1); pushup(rt); } node query(int l,int r,int rt,int L,int R){ if(l>=L&&r<=R){ return p[rt]; } int mid = (l + r)>>1; node t1,t2,res; t1.ans = -inf,t2.ans = -inf; if(mid >= L)t1 = query(l,mid,rt<<1,L,R); if(mid < R) t2 = query(mid+1,r,rt<<1|1,L,R); if(t1.ans!=-inf && t2.ans!=-inf){ res.lv = max(t1.lv, t1.v + t2.lv); res.rv = max(t2.rv, t2.v + t1.rv); res.v = t1.v + t2.v; res.ans = max3(t1.ans, t2.ans, t1.rv + t2.lv); } else if(t1.ans!=-inf){ res = t1; } else if(t2.ans!=-inf){ res = t2; } return res; } int main(){ int n,m; scanf("%d", &n); for(int i=1; i<=n; i++){ scanf("%d", &a[i]); } build(1,n,1); scanf("%d", &m); while(m--){ int l,r; scanf("%d%d", &l, &r); printf("%d\n", query(1,n,1,l,r).ans); }
GSS3 - Can you answer these queries III
增加修改而已。
inline void pushup(int o,int lc,int rc){ sum[o]=sum[lc]+sum[rc]; mx[o]=max(mx[lc],max(mx[rc],mxl[rc]+mxr[lc])); mxl[o]=max(mxl[lc],sum[lc]+mxl[rc]); mxr[o]=max(mxr[rc],sum[rc]+mxr[lc]);}void build(int o,int l,int r){ if(l==r){ mxl[o]=mx[o]=mxr[o]=sum[o]=a[l]; return; } int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1; build(lc,l,mid),build(rc,mid+1,r); pushup(o,lc,rc);}void update(int o,int l,int r){ if(l==r){ mxl[o]=mx[o]=mxr[o]=sum[o]=v; return; } int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1; if(le<=mid) update(lc,l,mid); else update(rc,mid+1,r); pushup(o,lc,rc);}void query(int o,int l,int r){ if(l>=le&&r<=ri){ ans=max(ans,max(frontx+mxl[o],mx[o])); frontx=max(frontx+sum[o],mxr[o]); return; } int mid=l+r>>1,lc=o<<1,rc=(o<<1)|1; if(le<=mid) query(lc,l,mid); if(ri>mid) query(rc,mid+1,r);}inline void req(){ ans=-inf,frontx=0; query(1,1,n); printf("%d\n",ans);}
