线段树进阶

给定一个长为n的序列A，满足每个位置都大于等于0。

现在有q次询问，每次询问分为两种：

• 1 l r c 表示给区间 A[l,r]加上c 。
• 2 v 表示询问最小的p满足A[1,p]的和大于或等于v 。

n,q≤10⁵

此题我相信各位dalao已经有了一个最简单的思路，对，没错，就是二分

10⁵二分怎么可能爆吗

在这道题中二分的复杂度很明显是O(n(logn)²)

但还是不够优秀要是这就完了我写这博文有何用

不难想出，我们可以更改查询的ask()函数将其改为在线段树上二分

由此省去一个log的复杂度

接下来就是实现的细节了

线段树上每个节点还是维护区间和

然后就对左子节点进行判断，区间和是否大于所求的值

如果大于等于，那就进入左子树继续搜

如果小于，那就所求的值减去左区间和，再进入右子树继续搜

代码奉上

int quep(int rt,int l,int r,int v){
    if(l==r) return l;
    pushdown(rt,r-l+1);
    int m = l+r>>1;
    if(T[rt*2]<v) return quep(rt*2+1,m+1,r,v-T[rt*2]);
    else return quep(rt*2,l,m,v);
}

给定一个长为n的序列A。

现在有q次询问，每次询问分为两种：

• 1 l r c 表示给区间A[l,r]加上c 。
• 2 v 表示询问最小的p满足A[1,p]的和大于或等于v。

n,q≤10⁵

乍一看，这不和上面一样吗？错大了！

这里没有限制数不能为负数

那么上一道题的代码会错在总区间和这一步

因为负数可以使这个区间和变小，但在负数之前的数的和可能已经达到了所求的数，那么就错了

同样，相信dalao们也会有个思路了

线段树上维护两个值s,t，

t为整个区间和，s为最大区间和

往下搜的时候就以s为主要条件

判断所求的值与s的大小

这样稍微处理了一下之后，就与上一道题没有什么区别了

int quep2(int rt,int l,int r,int v){
    if(l==r) return l;
    pushdown(rt,r-l+1);
    int m = l+r>>1;
    if(S[rt<<1]>=v) return quep2(rt<<1,l,m,v);
    else return quep2(rt<<1|1,m+1,r,v-T[rt<<1]);
}

给定一个长为n的序列A。

现在有q次询问，每次询问分为两种：

• 1 p c 表示将一个位置的值修改为c。
  
• 2 l r 对于区间[l,r]的子区间[L,R](l≤L≤R≤r)求出最大的A[L,R]的和。

n,q≤10⁵

这里就会复杂一些了，我们需要在每个节点上存储四个信息

最大区间和，整个区间的和，从最左端开始的连续区间最大的和，从最右端开始的连续区间最大的和

以下代码中，S是整个区间和，F是区间最大和，lS和rS就分别是从最左端开始的连续区间最大的和，从最右端开始的连续区间最大的和

lS的传递是从左儿子最大左区间和与整个左儿子加上有儿子的最大左区间和中的最大

只有这样才能保证左区间的连续性

rS同理

F可以选一个左右儿子中最大的，或者说是左儿子最大右区间加上右儿子最大左区间，依旧可以保证连续性

最后再将这个临时的结构体传回去就好了

struct node{
    int S,lS,rS,F;
}T[MAXN<<2];
node merge(node ls,node rs){
    node ret;
    ret.S = ls.S+rs.S;
    ret.lS = max(ls.lS,ls.S+rs.lS);
    ret.rS = max(rs.rS,rs.S+ls.rS);
    ret.F = max(ls.F,rs.F);
    ret.F = max(ret.F,ls.rS+rs.lS); 
    return ret;
}

给定一个长为n的序列A。

现在有q次询问，每次询问分为两种：

• 1 p c 表示将一个位置的值修改为c。
• 2 l r 对于区间[l,r]中的l≤i<j≤r 求出最大的A_j​−A_i​的和。

n,q≤10⁵

对每个区间维护最大值、最小值、最大极差即可合并。

从最左端开始的连续区间最大的和，从最右端开始的连续区间最大的和

原文地址：http://www.cnblogs.com/cztq/p/16909194.html