精华内容
下载资源
问答
  • #include #include using namespace std; int a[200000+10]; struct node{ int s,t,ma; struct node *l,*r; node(){ ma=0;l=NULL;r=NULL; } }; int js(struct node *h){ ... if(h->s==h->t){
    #include<iostream>
    #include<cstdio>
    using namespace std;
    int a[200000+10];
    struct node{
    	int s,t,ma;
    	struct node *l,*r;
    	node(){
    		ma=0;l=NULL;r=NULL;
    	}
    };
    int js(struct node *h){
    	struct node *p,*q;
    	if(h->s==h->t){
    		h->ma=a[h->s];return h->ma;		
    	}
    	p=new node;p->s=h->s;p->t=(h->s+h->t)/2;
    	q=new node;q->s=(h->s+h->t)/2+1;q->t=h->t;
    	h->l=p;h->r=q;
    	int x=js(p);int y=js(q);
    	h->ma=max(x,y);
    	return h->ma;		
    }
    int dfs(node *h,int x,int y){
    	if(y<h->s || x>h->t)return 0;
    	if(x<=h->s && y>=h->t)return h->ma;
    	int x1=dfs(h->l,x,y);int x2=dfs(h->r,x,y);
    	return max(x1,x2);
    }
    int up(node *h,int x){	
    	if(h->s==h->t && h->s==x){
    		h->ma=a[x];return h->ma;
    	};
    	if(x<h->s || x>h->t)return h->ma;
    	int x1=up(h->l,x);
    	int x2=up(h->r,x);
    	h->ma=max(x1,x2);
    	return h->ma;
    }
    int main(){	
    	int n,m;
    	while(scanf("%d%d",&n,&m)!=EOF){
    		struct node *h;
    		for(int i=1;i<=n;i++)scanf("%d",&a[i]);
    		h=new node;h->s=1;h->t=n;
    		js(h);
    		for(int i=1;i<=m;i++){
    			char c;int x,y;
    			getchar();
    			scanf("%c %d %d",&c,&x,&y);
    			if(c=='Q'){
    				printf("%d\n",dfs(h,x,y));	
    			}
    			if(c=='U'){
    				a[x]=y;
    				up(h,x);
    			}
    		}	
    	}
    	return 0;
    }

    展开全文
  • 线段树 从入门到进阶(清晰,简单易懂)

    万次阅读 多人点赞 2020-02-12 11:08:57
    目录第一部 概念引入第二部 简单(无pushdown)的线段树1、单点修改,区间查询2、区间修改,单点查询第三部 进阶线段树第四部 乘法(根号)线段树1、乘法线段树2、根号线段树模板题与代码:单点修改,区间查询:洛谷...

    线段树是什么??线段树怎么写??

    如果你在考提高组前一天还在问这个问题,那么你会与一等奖失之交臂;如果你还在冲击普及组一等奖,那么这篇博客会浪费你人生中宝贵的5~20分钟。

    上面两句话显而易见,线段树这个数据结构是一个从萌新到正式OI选手的过渡,是一个非常重要的算法,也是一个对于萌新来说较难的算法。不得不说,我学习了这个算法5遍左右才有勇气写的这篇博客。

    但是,对于OI正式选手来说,线段树不是算法,应该是一种工具。她能把一些对于区间(或者线段)的修改、维护,从O(N)的时间复杂度变成O(logN)

    第一部:线段树概念引入

    第二部:简单(无pushdown)的线段树

    第三部:区间+/-修改与查询

    第四部:区间乘除修改与查询

    第一部 概念引入

    线段树是一种二叉树,也就是对于一个线段,我们会用一个二叉树来表示。比如说一个长度为4的线段,我们可以表示成这样:

    在这里插入图片描述

    这是什么意思呢? 如果你要表示线段的和,那么最上面的根节点的权值表示的是这个线段1-4的和。根的两个儿子分别表示这个线段中1-2的和,与2-3的和。以此类推。

    然后我们还可以的到一个性质:节点i的权值=她的左儿子权值+她的右儿子权值。因为1-4的和就是等于1-2的和2-3的和。

    根据这个思路,我们就可以建树了,我们设一个结构体treetree[i].l和tree[i].r分别表示这个点代表的线段的左右下标,tree[i].sum表示这个节点表示的线段和。

    我们知道,一颗二叉树,她的左儿子和右儿子编号分别是她*2和她*2+1

    再根据刚才的性质,得到式子: t r e e [ i ] . s u m = t r e e [ i ∗ 2 ] . s u m + t r e e [ i ∗ 2 + 1 ] . s u m ; tree[i].sum=tree[i*2].sum+tree[i*2+1].sum; tree[i].sum=tree[i2].sum+tree[i2+1].sum;就可以建一颗线段树了!代码如下:

    inline void build(int i,int l,int r){//递归建树
        tree[i].l=l;tree[i].r=r;
        if(l==r){//如果这个节点是叶子节点
            tree[i].sum=input[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(i*2,l,mid);//分别构造左子树和右子树
        build(i*2+1,mid+1,r);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//刚才我们发现的性质return ;
    }
    

    嗯,这就是线段树的构建,你可能会问为什么要开好几倍的内存去储存一条线段。这是因为我们还没有让这个过大的数组干一些实事,那么什么是实事呢?让我们进入下一部(在你看懂这一部的情况下)

    第二部 简单(无pushdown)的线段树

    1、单点修改,区间查询

    其实这一章开始才是真正的线段树,我们要用线段树干什么?答案是维护一个线段(或者区间),比如你想求出一个1100区间中,467这些元素的和,你会怎么做?朴素的做法是for(i=4;i<=67;i++) sum+=a[i],这样固然好,但是算得太慢了。

    我们想一种新的方法,先想一个比较好画图的数据,比如一个长度为4的区间,分别是1、2、3、4,我们想求出第1~3项的和。按照上一部说的,我们要建出一颗线段树,其中点权(也就是红色)表示和:

    在这里插入图片描述

    然后我们要求1-3的和,我们先从根节点开始查询,发现她的左儿子1-2这个区间和答案区间1~3有交集,那么我们跑到左儿子这个区间。

    然后,我们发现这个区间1-2被完全包括在答案区间1~3这个区间里面,那就把她的值3返回。

    我们回到了1-4区间,发现她的右儿子3-4区间和答案区间1~3有交集,那么我们走到3-4区间

    到了3-4区间,我们发现她并没有完全包含在答案区间1-3里面,但发现她的左儿子3-3区间和1~3区间又交集,那么久走到3-3区间

    到了3~3区间,发现其被答案区间完全包含,就返回她的值3一直到最开始

    3-3区间的3+1-2区间的3=6,我们知道了1~3区间和为6.

    有人可能会说你这样是不是疯了,我那脚都能算出1+2+3=6,为什么这么麻烦?!

    因为这才几个数,如果一百万个数,这样时间会大大增快。

    我们总结一下,线段树的查询方法:

    1. 如果这个区间被完全包括在目标区间里面,直接返回这个区间的值

    2. 如果这个区间的左儿子和目标区间有交集,那么搜索左儿子

    3. 如果这个区间的右儿子和目标区间有交集,那么搜索右儿子

    写成代码,就会变成这样:

    inline int search(int i,int l,int r){
        if(tree[i].l>=l && tree[i].r<=r)//如果这个区间被完全包括在目标区间里面,直接返回这个区间的值
            return tree[i].sum;
        if(tree[i].r<l || tree[i].l>r)  return 0;//如果这个区间和目标区间毫不相干,返回0
        int s=0;
        if(tree[i*2].r>=l)  s+=search(i*2,l,r);//如果这个区间的左儿子和目标区间又交集,那么搜索左儿子
        if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);//如果这个区间的右儿子和目标区间又交集,那么搜索右儿子
        return s;
    }
    

    关于那几个if的条件一定要看清楚,最好背下来,以防考场上脑抽推错。

    然后,我们怎么修改这个区间的单点,其实这个相对简单很多,你要把区间的第dis位加上k。

    那么你从根节点开始,看这个dis是在左儿子还是在右儿子,在哪往哪跑,

    然后返回的时候,还是按照tree[i].sum=tree[i*2].sum+tree[i*2+1].sum的原则,更新所有路过的点

    如果不理解,我还是画个图吧,其中深蓝色是去的路径,浅蓝色是返回的路径,回来时候红色的+标记就是把这个点加上这个值。

    在这里插入图片描述

    把这个过程变成代码,就是这个样子:

    inline void add(int i,int dis,int k){
        if(tree[i].l==tree[i].r){//如果是叶子节点,那么说明找到了
            tree[i].sum+=k;
            return ;
        }
        if(dis<=tree[i*2].r)  add(i*2,dis,k);//在哪往哪跑
        else  add(i*2+1,dis,k);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//返回更新
        return ;
    }
    

    2、区间修改,单点查询

    区间修改和单点查询,我们的思路就变为:如果把这个区间加上k,相当于把这个区间涂上一个k的标记,然后单点查询的时候,就从上跑道下,把沿路的标记加起来就好。

    这里面给区间贴标记的方式与上面的区间查找类似,原则还是那三条,只不过第一条:如果这个区间被完全包括在目标区间里面,直接返回这个区间的值变为了如果这个区间如果这个区间被完全包括在目标区间里面,讲这个区间标记k

    具体做法很像,这里贴上代码:

    inline void add(int i,int l,int r,int k){
        if(tree[i].l>=l && tree[i].r<=r){//如果这个区间被完全包括在目标区间里面,讲这个区间标记k
            tree[i].sum+=k;
            return ;
        }
        if(tree[i*2].r>=l)
            add(i*2,l,r,k);
        if(tree[i*2+1].l<=r)
            add(i*2+1,l,r,k);
    }
    

    然后就是单点查询了,这个更好理解了,就是dis在哪往哪跑,把路径上所有的标价加上就好了:

    void search(int i,int dis){
        ans+=tree[i].sum;//一路加起来
        if(tree[i].l==tree[i].r)
            return ;
        if(dis<=tree[i*2].r)
            search(i*2,dis);
        if(dis>=tree[i*2+1].l)
            search(i*2+1,dis);
    }
    

    完整测试代码:

    #include <bits/stdc++.h>
    using namespace std;
    const int maxn = 1e5 + 7;
    
    int n, m, s, t;
    int ans;
    int a[maxn];
    struct segment_tree
    {	
    	struct node
    	{
    		int l, r;
    		int num;
    	}tr[maxn];
    	
    	void build(int p, int l, int r)
    	{
    		tr[p] = {l, r, 0};
    		if(l == r) {
    			tr[p].num = a[l];
    			return ;
    		}
    		int mid = l + r >> 1;
    		build(p << 1, l, mid);
    		build(p << 1 | 1, mid + 1, r);
    	}		
    	
    	void modify(int p, int l, int r, int k) 
    	{
    		if(tr[p].l >= l && tr[p].r <= r) {
    			tr[p].num += k;
    			return ;
    		}
    		int mid = tr[p].l + tr[p].r >> 1;
    		if(l <= mid) modify(p << 1, l, r, k);
    		if(r > mid) modify(p << 1 | 1, l, r, k);
    	}
    	
    	void query(int p, int x)
    	{
    		ans += tr[p].num;
    		if(tr[p].l == tr[p].r) return 	;
    		int mid = tr[p].l + tr[p].r >> 1;
    		if(x <= mid) query(p << 1, x);
    		else query(p << 1 | 1, x); 
    	}
    }ST;
    
    int main()
    {
    	n = 100;
    	for (int i = 1; i <= n; ++ i) {
    		a[i] = i;
    	}
    	ST.build(1, 1, n);
    	m = 10;
    	while(m -- ) {
    		int l = 1, r = 100;
    		ST.modify(1, l, r, 10000);
    		ans = 0;
    		ST.query(1, 50);
    		//cout << ans << endl;
    		ans = 0;
    		ST.query(1, 100);
    		cout << ans << endl;
    	}
    	return 0;
    }
    

    输入:

    (无)
    

    输出:

    10100
    20100
    30100
    40100
    50100
    60100
    70100
    80100
    90100
    100100
    
    

    不知不觉,这第二章已经结束。这样的简单(原谅我用这个词)线段树,还可除了求和,还可以求区间最小最大值,还可以区间染色。

    但是!这样的线段树展现不出来她的魅力,因为区间求和,树状数组比她少了一个很大的常数。二区间最值,ST表的那神乎其技 O ( 1 ) O(1) O(1) 查询也能完爆她。这是为什么?因为线段树的魅力还没有展现出来,她最美丽的地方:pushdown还未展现于世,如果你已经对这一章充足的了解,并且能不看博客把洛谷上树状数组模板1、2都能写出来,那么请你进入下一部。

    第三部 进阶线段树

    区间修改、区间查询,你可能会认为,把上一章里面的这两个模块加在一起就好了,然后你就会发现你大错特错。

    因为如果对于1~4这个区间,你把1~3区间+1,相当于把节点1~2和3标记,但是如果你查询2~4时,你会发现你加的时没有标记的2节点和没有标记的3~4节点加上去,结果当然是错的。

    那么我们应该怎么办?这时候pushdown的作用就显现出来了。

    你会想到,我们只需要在查询的时候,如果我们要查的2节点在1~2区间的里面,那我们就可以把1~2区间标记的那个+1给推下去这样就能顺利地加上了。
    怎么记录这个标记呢?我们需要记录一个“懒标记”lazytage,来记录这个区间

    区间修改的时候,我们按照如下原则:

    1、如果当前区间被完全覆盖在目标区间里,讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
    
    2、如果没有完全覆盖,则先下传懒标记
    
    3、如果这个区间的左儿子和目标区间有交集,那么搜索左儿子
    
    4、如果这个区间的右儿子和目标区间有交集,那么搜索右儿子
    

    然后查询的时候,将这个懒标记下传就好了,下面图解一下:

    如图,区间1-4分别是1、2、3、4,我们要把1-3区间+1。因为1~2区间被完全覆盖,所以将其+2,并将紫色的lazytage+1,3区间同理

    在这里插入图片描述

    注意我们处理完这些以后,还是要按照tree[i].sum=tree[i*2].sum+tree[i*2+1].sum的原则返回,代码如下:

    void add(int i,int l,int r,int k)
    {
        if(tree[i].r<=r && tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里,讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
        {
            tree[i].sum+=k*(tree[i].r-tree[i].l+1);
            tree[i].lz+=k;//记录lazytage
            return ;
        }
        push_down(i);//向下传递
        if(tree[i*2].r>=l)
            add(i*2,l,r,k);
        if(tree[i*2+1].l<=r)
            add(i*2+1,l,r,k);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
        return ;
    }
    

    其中的pushdown,就是把自己的lazytage归零,并给自己的儿子加上,并让自己的儿子加上k*(r-l+1)

    void push_down(int i)
    {
        if(tree[i].lz!=0)
        {
            tree[i*2].lz+=tree[i].lz;//左右儿子分别加上父亲的lz
            tree[i*2+1].lz+=tree[i].lz;
            int mid=(tree[i].l+tree[i].r)/2;
            tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);//左右分别求和加起来
            tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
            tree[i].lz=0;//父亲lz归零
        }
        return ;
    }
    

    查询的时候,和上一章的几乎一样,就是也要像修改一样加入pushdown,这里用图模拟一下。我们要查询2~4区间的和,这是查询前的情况,所有紫色的代表lazytage

    在这里插入图片描述

    然后,我们查到区间1~2时,发现这个区间并没有被完全包括在目标区间里,于是我们就pushdown,lazytage下传,并让每个区间sum加上(r-l)*lazytage。

    在这里插入图片描述

    然后查到2-2区间,发现被完全包含,所以就返3,再搜索到3~4区间,发现被完全包含,那么直接返回8,最后3+8=11就是答案

    这里是代码实现:

    inline int search(int i,int l,int r){
        if(tree[i].l>=l && tree[i].r<=r)
            return tree[i].sum;
        if(tree[i].r<l || tree[i].l>r)  return 0;
        push_down(i);
        int s=0;
        if(tree[i*2].r>=l)  s+=search(i*2,l,r);
        if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);
        return s;
    }
    

    好了,到了这里,我们就学会了用线段树进行区间加减操作,大家可以完成洛谷的线段树模板1.

    第四部 乘法(根号)线段树

    1、乘法线段树

    如果这个线段树只有乘法,那么直接加入lazytage变成乘,然后tree[i].sum*=k就好了。但是,如果我们是又加又乘,那就不一样了。

    当lazytage下标传递的时候,我们需要考虑,是先加再乘还是先乘再加。我们只需要对lazytage做这样一个处理。

    lazytage分为两种,分别是加法的plz和乘法的mlz。

    mlz很简单处理,pushdown时直接*父亲的就可以了,那么加法呢?

    我们需要把原先的plz*父亲的mlz再加上父亲的plz.

    inline void pushdown(long long i){//注意这种级别的数据一定要开long long
        long long k1=tree[i].mlz,k2=tree[i].plz;
        tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;//
        tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
        tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
        tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
        tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
        tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
        tree[i].plz=0;
        tree[i].mlz=1;
        return ;
    }
    

    然后加法和减法的函数同理,维护lazytage的时候加法标记一定要记得现乘再加。

    值得一提的是,计算*2时一定要改成i<<1这样能解决很多时间,还有要开long long,还有,函数前面要加inline 我在其他OJ交这道题时,就因为没加inline 就被卡了,交了就过了。

    2、根号线段树

    其实,根号线段树和除法线段树一样。她们乍眼一看感觉直接用lazytage标记除了多少,但是实际上,会出现精度问题。

    c++的除法是向下取整,很明显,(a+b)/k!=a/k+b/k(在向下取整的情况下),而根号,很明显根号(a)+根号(b)!=根号(a+b)那么怎么办?

    第一个想法就是暴力,对于每个要改动的区间l~r,把里面的每个点都单独除,但这样就会把时间复杂度卡得比大暴力都慢(因为多个常数),所以怎么优化?

    我们对于每个区间,维护她的最大值和最小值,然后每次修改时,如果这个区间的最大值根号和最小值的根号一样,说明这个区间整体根号不会产生误差,就直接修改(除法同理)

    其中,lazytage把除法当成减法,记录的是这个区间里每个元素减去的值。

    下面是根号线段树的修改过程:

    inline void Sqrt(int i,int l,int r){
        if(tree[i].l>=l && tree[i].r<=r && (tree[i].minn-(long long)sqrt(tree[i].minn))==(tree[i].maxx-(long long)sqrt(tree[i].maxx))){//如果这个区间的最大值最小值一样
            long long u=tree[i].minn-(long long)sqrt(tree[i].minn);//计算区间中每个元素需要减去的
            tree[i].lz+=u;
            tree[i].sum-=(tree[i].r-tree[i].l+1)*u;
            tree[i].minn-=u;
            tree[i].maxx-=u;
                //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
            return ;
        }
        if(tree[i].r<l || tree[i].l>r)  return ;
        push_down(i);
        if(tree[i*2].r>=l)  Sqrt(i*2,l,r);
        if(tree[i*2+1].l<=r)  Sqrt(i*2+1,l,r);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
        tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);//维护最大值和最小值
        tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
        //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
        return ;
    }
    

    然后pushdown没什么变化,就是要记得tree[i].minn、tree[i].maxx也要记得-lazytage。


    附赠一份支持单点修改,区间取相反数,区间最小值,区间最大值的线段树代码

    题目链接:https://www.luogu.com.cn/problem/P1505

    题解:BZOJ 2157 「国家集训队」旅游(树链剖分,线段树,边权转点权)

    struct Segment_Tree
    {
    	struct node 
    	{
    		int l, r;
    		int sum;
    //		int laz; 
    		int tag;//相反数的tag
    		int maxx;
    		int minn;
    	}tr[maxn << 2];
    	
    	void pushup(int p)
    	{
    		node &l = tr[p << 1], &r = tr[p << 1 | 1], &rt = tr[p];
    		rt.sum = l.sum + r.sum;
    		rt.maxx = max(l.maxx, r.maxx);
    		rt.minn = min(l.minn, r.minn);
    	}
    	
    	void pushdown(int p)
    	{
    		node &l = tr[p << 1], &r = tr[p << 1 | 1], &rt = tr[p];
    		if(rt.tag == 0) return ;
    		l.tag ^= 1, r.tag ^= 1;
    		l.sum = -l.sum, r.sum = -r.sum;
    		l.maxx = -l.maxx, r.maxx = -r.maxx;
    		l.minn = -l.minn, r.minn = -r.minn;
    		swap(l.maxx, l.minn), swap(r.maxx, r.minn);
    		rt.tag = 0;
    	}
    	
    	void build(int p, int l, int r)
    	{
    		tr[p].l = l, tr[p].r = r;
    		if(l == r) {
    			tr[p].sum = tr[p].minn = tr[p].maxx = a_after[l];
    			return ;
    		}	
    		int mid = l + r >> 1;
    		build(p << 1, l, mid);
    		build(p << 1 | 1, mid + 1, r);
    		pushup(p);
    	}
    	
    	void modify(int p, int x, int k)
    	{
    		if(tr[p].l == tr[p].r) {
    			tr[p].sum = tr[p].minn = tr[p].maxx = k;
    			return ;
    		}
    		if(tr[p].tag) pushdown(p);
    		int mid = tr[p].l + tr[p].r >> 1;
    		if(x <= mid) modify(p << 1, x, k);
    		if(x > mid) modify(p << 1 | 1, x, k);
    		pushup(p);
    	}
    	
    	void _reverse(int p, int l, int r)
    	{
    		if(tr[p].l >= l && tr[p].r <= r) {
    			tr[p].tag ^= 1;
    			tr[p].sum = -tr[p].sum;
    			tr[p].minn = -tr[p].minn;
    			tr[p].maxx = -tr[p].maxx;
    			swap(tr[p].minn, tr[p].maxx);
    			return ;
    		}
    		if(tr[p].tag) pushdown(p);
    		int mid = tr[p].l + tr[p].r >> 1;
    		if(l <= mid) _reverse(p << 1, l, r);
    		if(r > mid) _reverse(p << 1 | 1, l, r);
    		pushup(p);
    	}
    	
    	int query_sum(int p, int l, int r)
    	{
    		int res = 0;
    		if(tr[p].l >= l && tr[p].r <= r) return tr[p].sum;
    		if(tr[p].tag) pushdown(p);
    		int mid = tr[p].l + tr[p].r >> 1;
    		if(l <= mid) res += query_sum(p << 1, l, r);
    		if(r > mid) res += query_sum(p << 1 | 1, l, r);
    		pushup(p);
    		return res;
    	}
    	
    	int query_max(int p, int l, int r)
    	{
    		int res = -INF;
    		if(tr[p].l >= l && tr[p].r <= r) return tr[p].maxx;
    		if(tr[p].tag) pushdown(p);
    		int mid = tr[p].l + tr[p].r >> 1;
    		if(l <= mid) res = max(res, query_max(p << 1, l, r));
    		if(r > mid) res = max(res, query_max(p << 1 | 1, l, r));
    		pushup(p);
    		return res;
    	}
    	
    	int query_min(int p, int l, int r)
    	{
    		int res = INF;
    		if(tr[p].l >= l && tr[p].r <= r) return tr[p].minn;
    		if(tr[p].tag) pushdown(p);
    		int mid = tr[p].l + tr[p].r >> 1;
    		if(l <= mid) res = min(res, query_min(p << 1, l, r));
    		if(r > mid) res = min(res, query_min(p << 1 | 1, l, r));
    		pushup(p);
    		return res;
    	} 
    }ST; 
    

    模板题与代码:

    最后,我们给几道模板题,再贴上代码:

    单点修改,区间查询:洛谷树状数组模板1

    P3374 【模板】树状数组 1

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #include <cstdlib>
    #include <queue>
    #include <stack>
    #include <vector>
    using namespace std;
    #define MAXN 100010
    #define INF 10000009
    #define MOD 10000007
    #define LL long long
    #define in(a) a=read()
    #define REP(i,k,n) for(long long i=k;i<=n;i++)
    #define DREP(i,k,n) for(long long i=k;i>=n;i--)
    #define cl(a) memset(a,0,sizeof(a))
    inline long long read(){
        long long x=0,f=1;char ch=getchar();
        for(;!isdigit(ch);ch=getchar()) if(ch=='-') f=-1;
        for(;isdigit(ch);ch=getchar()) x=x*10+ch-'0';
        return x*f;
    }
    inline void out(long long x){
        if(x<0) putchar('-'),x=-x;
        if(x>9) out(x/10);
        putchar(x%10+'0');
    }
    long long n,m,p;
    long long input[MAXN];
    struct node{
        long long l,r;
        long long sum,mlz,plz;
    }tree[4*MAXN];
    inline void build(long long i,long long l,long long r){
        tree[i].l=l;
        tree[i].r=r;
        tree[i].mlz=1;
        if(l==r){
            tree[i].sum=input[l]%p;
            return ;
        }
        long long mid=(l+r)>>1;
        build(i<<1,l,mid);
        build(i<<1|1,mid+1,r);
        tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
        return ;
    }
    inline void pushdown(long long i){
        long long k1=tree[i].mlz,k2=tree[i].plz;
        tree[i<<1].sum=(tree[i<<1].sum*k1+k2*(tree[i<<1].r-tree[i<<1].l+1))%p;
        tree[i<<1|1].sum=(tree[i<<1|1].sum*k1+k2*(tree[i<<1|1].r-tree[i<<1|1].l+1))%p;
        tree[i<<1].mlz=(tree[i<<1].mlz*k1)%p;
        tree[i<<1|1].mlz=(tree[i<<1|1].mlz*k1)%p;
        tree[i<<1].plz=(tree[i<<1].plz*k1+k2)%p;
        tree[i<<1|1].plz=(tree[i<<1|1].plz*k1+k2)%p;
        tree[i].plz=0;
        tree[i].mlz=1;
        return ;
    }
    inline void mul(long long i,long long l,long long r,long long k){
        if(tree[i].r<l || tree[i].l>r)  return ;
        if(tree[i].l>=l && tree[i].r<=r){
            tree[i].sum=(tree[i].sum*k)%p;
            tree[i].mlz=(tree[i].mlz*k)%p;
            tree[i].plz=(tree[i].plz*k)%p;
            return ;
        }
        pushdown(i);
        if(tree[i<<1].r>=l)  mul(i<<1,l,r,k);
        if(tree[i<<1|1].l<=r)  mul(i<<1|1,l,r,k);
        tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
        return ;
    }
    inline void add(long long i,long long l,long long r,long long k){
        if(tree[i].r<l || tree[i].l>r)  return ;
        if(tree[i].l>=l && tree[i].r<=r){
            tree[i].sum+=((tree[i].r-tree[i].l+1)*k)%p;
            tree[i].plz=(tree[i].plz+k)%p;
            return ;
        }
        pushdown(i);
        if(tree[i<<1].r>=l)  add(i<<1,l,r,k);
        if(tree[i<<1|1].l<=r)  add(i<<1|1,l,r,k);
        tree[i].sum=(tree[i<<1].sum+tree[i<<1|1].sum)%p;
        return ;
    }
    inline long long search(long long i,long long l,long long r){
        if(tree[i].r<l || tree[i].l>r)  return 0;
        if(tree[i].l>=l && tree[i].r<=r)
            return tree[i].sum;
        pushdown(i);
        long long sum=0;
        if(tree[i<<1].r>=l)  sum+=search(i<<1,l,r)%p;
        if(tree[i<<1|1].l<=r)  sum+=search(i<<1|1,l,r)%p;
        return sum%p;
    }
    int main(){
        in(n);    in(m);in(p);
        REP(i,1,n)  in(input[i]);
        build(1,1,n); 
    
        REP(i,1,m){
            long long fl,a,b,c;
            in(fl);
            if(fl==1){
                in(a);in(b);in(c);
                c%=p;
                mul(1,a,b,c);
            }
            if(fl==2){
                in(a);in(b);in(c);
                c%=p;
                add(1,a,b,c);
            }
            if(fl==3){
                in(a);in(b);
                printf("%lld\n",search(1,a,b));
            }
        }
        return 0;
    }
    /*
    5 4 1000
    1 2 3 4 5
    3 1 5
    2 1 5 1
    1 1 5 2
    
    3 1 5
    */ 
    

    区间修改,单点查询:洛谷树状数组模板2

    P3368 【模板】树状数组 2

    #include <iostream>
    #include <algorithm>
    #include <cstdio>
    #include <cstring>
    #include <cmath>
    #include <queue>
    using namespace std;
    int n,m;
    int ans;
    int input[500010];
    struct node
    {
        int left,right;
        int num;
    }tree[2000010];
    void build(int left,int right,int index)
    {
        tree[index].num=0;
        tree[index].left=left;
        tree[index].right=right;
           if(left==right)
            return ;
        int mid=(right+left)/2;
        build(left,mid,index*2);
        build(mid+1,right,index*2+1);
    }
    void pls(int index,int l,int r,int k)
    {
        if(tree[index].left>=l && tree[index].right<=r)
        {
            tree[index].num+=k;
            return ;
        }
        if(tree[index*2].right>=l)
           pls(index*2,l,r,k);
        if(tree[index*2+1].left<=r)
           pls(index*2+1,l,r,k);
    }
    void search(int index,int dis)
    {
        ans+=tree[index].num;
        if(tree[index].left==tree[index].right)
            return ;
        if(dis<=tree[index*2].right)
            search(index*2,dis);
        if(dis>=tree[index*2+1].left)
            search(index*2+1,dis);
    }
    int main()
    {
        int n,m;
        cin>>n>>m;
        build(1,n,1);
        for(int i=1;i<=n;i++)
            scanf("%d",&input[i]);
        for(int i=1;i<=m;i++)
        {
            int a;
            scanf("%d",&a);
            if(a==1)
            {
                int x,y,z;
                scanf("%d%d%d",&x,&y,&z);
                pls(1,x,y,z);
            }
            if(a==2)
            {
                ans=0;
                int x;
                scanf("%d",&x);
                search(1,x);
                printf("%d\n",ans+input[x]);
            }
        }
    }
    

    区间加法,洛谷线段树模板1

    P3372 【模板】线段树 1

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll N=1e6+7;
    const ll mod=2147483647;
    ll n,m;
    struct node
    {
        ll l,r,sum,lz;
    }tree[N];
    ll arr[N];
    void build(ll i,ll l,ll r,ll arr[])
    {
        tree[i].lz=0;//初始化的时候肯定都是0
        tree[i].l=l;
        tree[i].r=r;
        if(l==r)
        {
            tree[i].sum=arr[l];//到达底部单节点才把输入的值赋给你
            return ;
        }
        ll mid=(l+r)/2;
        build(i*2,l,mid,arr);
        build(i*2+1,mid+1,r,arr);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//树已经全部建完了,再从下往上+++,使得上层的树都有了值
        return ;
    }
    inline void push_down(ll i)
    {
        if(tree[i].lz!=0)
        {
            tree[i*2].lz+=tree[i].lz;
            tree[i*2+1].lz+=tree[i].lz;
            ll mid=(tree[i].l+tree[i].r)/2;
            tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);
            tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
            tree[i].lz=0;
        }
        return ;
    }
    inline void add(ll i,ll l,ll r,ll k)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
        {
            tree[i].sum+=k*(tree[i].r-tree[i].l+1);
            tree[i].lz+=k;
            return ;
        }
        push_down(i);
        if(tree[i*2].r>=l)
            add(i*2,l,r,k);
        if(tree[i*2+1].l<=r)
            add(i*2+1,l,r,k);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
        return ;
    }
    inline ll searchs(ll i,ll l, ll r)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
            return tree[i].sum;
        push_down(i);
        ll num=0;
        if(tree[i*2].r>=l)
            num+=searchs(i*2,l,r);
        if(tree[i*2+1].l<=r)
            num+=searchs(i*2+1,l,r);
        return num;
    }
    int main()
    {
        ios::sync_with_stdio(false);
        cin.tie(0),cout.tie(0);
        cin>>n>>m;
        for(int i=1;i<=n;++i)
            cin>>arr[i];
        build(1,1,n,arr);//从根节点开始建树
        for(int i=1;i<=m;++i)
        {
            ll tmp;
            cin>>tmp;
            if(tmp==1)
            {
                ll a,b,c;
                cin>>a>>b>>c;
                add(1,a,b,c);//每次修改都是从编号为1开始的,因为编号1是树的顶端,往下分叉
            }
            if(tmp==2)
            {
                ll a,b;
                cin>>a>>b;
                printf("%lld\n",searchs(1,a,b));//编号i的话,每次都是从1开始
            }
        }
        return 0;
    }
    

    区间乘法:洛谷线段树模板2

    P3373 【模板】线段树 2

    #include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    const ll N=1e6+7;
    template<typename T>void read(T &x)
    {
        x=0;char ch=getchar();ll f=1;
        while(!isdigit(ch)){if(ch=='-')f=-1;ch=getchar();}
        while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}x*=f;
    }
    ll n,m,arr[N],mod,flag,cn,cm,cw;
    struct node
    {
        ll l,r,sum,mul,add;//有乘有加,先乘后加
    }tree[N];
    
    inline void build(ll i,ll l,ll r)
    {
        tree[i].l=l;
        tree[i].r=r;
        tree[i].mul=1;
        if(l==r)
        {
            tree[i].sum=arr[l]%mod;
            return ;
        }
        ll mid=(l+r)>>1;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
    }
    inline void push_down(ll i)
    {
        tree[i*2].sum=(ll)(tree[i].mul*tree[i*2].sum+((tree[i*2].r-tree[i*2].l+1)*tree[i].add)%mod)%mod;
        tree[i*2+1].sum=(ll)(tree[i].mul*tree[i*2+1].sum+((tree[i*2+1].r-tree[i*2+1].l+1)*tree[i].add)%mod)%mod;
        tree[i*2].mul=(ll)(tree[i*2].mul*tree[i].mul)%mod;
        tree[i*2+1].mul=(ll)(tree[i*2+1].mul*tree[i].mul)%mod;
        tree[i*2].add=(ll)(tree[i*2].add*tree[i].mul+tree[i].add)%mod;
        tree[i*2+1].add=(ll)(tree[i*2+1].add*tree[i].mul+tree[i].add)%mod;
        tree[i].mul=1;tree[i].add=0;
    }
    inline void add(ll i,ll l,ll r,ll k)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
        {
            tree[i].add=(ll)(tree[i].add+k)%mod;
            tree[i].sum=(ll)(tree[i].sum+k*(tree[i].r-tree[i].l+1))%mod;
            return ;
        }
        push_down(i);
      
        if(tree[i*2].r>=l)
            add(i*2,l,r,k);
        if(tree[i*2+1].l<=r)
            add(i*2+1,l,r,k);
        //ll mid=(tree[i].l+tree[i].r)>>1;
        //if(l<=mid)add(i*2,l,r,k);
        //if(mid<r)add(i*2+1,l,r,k);
        tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
    }
    inline void mult(ll i,ll l,ll r,ll k)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
        {
            tree[i].mul=(tree[i].mul*k)%mod;
            tree[i].add=(tree[i].add*k)%mod;
            tree[i].sum=(tree[i].sum*k)%mod;
            return ;
        }
        push_down(i);
      
        if(tree[i*2].r>=l)
            mult(i*2,l,r,k);
        if(tree[i*2+1].l<=r)
            mult(i*2+1,l,r,k);
        //ll mid=(tree[i].l+tree[i].r)>>1;
        //if(l<=mid)mult(i*2,l,r,k);
        //if(mid<r)mult(i*2+1,l,r,k);
        tree[i].sum=(tree[i*2].sum+tree[i*2+1].sum)%mod;
    }
    inline ll query(ll i,ll l,ll r)
    {
        if(tree[i].l>=l&&tree[i].r<=r)
            return tree[i].sum;
        push_down(i);
        ll num=0;
        if(tree[i*2].r>=l)
            num=(num+query(i*2,l,r))%mod;
        if(tree[i*2+1].l<=r)
            num=(num+query(i*2+1,l,r))%mod;
        return num;
        //ll val=0;
        //ll mid=(tree[i].l+tree[i].r)>>1;
        //if(l<=mid)val=(val+query(i*2,l,r))%mod;
        //if(mid<r)val=(val+query(i*2+1,l,r))%mod;
        //return val;
    }
    int main()
    {
        read(n),read(m),read(mod);
        for(int i=1;i<=n;++i)
            read(arr[i]);
        build(1,1,n);
        for(int i=1;i<=m;++i)
        {
            read(flag);
            if(flag==1)
            {
                read(cn),read(cm),read(cw);
                mult(1,cn,cm,cw);
            }
            else if(flag==2){
                read(cn),read(cm),read(cw);
                add(1,cn,cm,cw);
            }
            else {
                read(cn),read(cm);
                cout<<query(1,cn,cm)<<endl;
            }
        }
    }
    /*
    5 4 1000
    1 2 3 4 5
    3 1 5
    2 1 5 1
    1 1 5 2
    
    3 1 5
    */ 
    

    区间根号,bzoj3211

    #include <iostream>
    #include <cstdio>
    #include <algorithm>
    #include <cstring>
    #include <cmath>
    #define MAXN 1000010
    #define REP(i,k,n) for(int i=k;i<=n;i++)
    #define in(a) a=read()
    using namespace std;
    int read(){
        int x=0,f=1;
        char ch=getchar();
        for(;!isdigit(ch);ch=getchar())
            if(ch=='-')
              f=-1;
        for(;isdigit(ch);ch=getchar())
            x=x*10+ch-'0';
        return x*f;
    }
    struct node{
        int l,r;
        long long lz,sum,maxx,minn;
    }tree[MAXN<<2];
    int n,m,input[MAXN];
    inline void build(int i,int l,int r){
        tree[i].l=l;tree[i].r=r;
        if(l==r){
            tree[i].sum=tree[i].minn=tree[i].maxx=input[l];
            return ;
        }
        int mid=(l+r)>>1;
        build(i*2,l,mid);
        build(i*2+1,mid+1,r);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
        tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
        tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
        return ;
    }
    inline void push_down(int i){
        if(!tree[i].lz)  return ;
        long long k=tree[i].lz;
        tree[i*2].lz+=k;
        tree[i*2+1].lz+=k;
        tree[i*2].sum-=(tree[i*2].r-tree[i*2].l+1)*k;
        tree[i*2+1].sum-=(tree[i*2+1].r-tree[i*2+1].l+1)*k;
        tree[i*2].minn-=k;
        tree[i*2+1].minn-=k;
        tree[i*2].maxx-=k;
        tree[i*2+1].maxx-=k;
        tree[i].lz=0;
        return ;
    }
    inline void Sqrt(int i,int l,int r){
        if(tree[i].l>=l && tree[i].r<=r && (tree[i].minn-(long long)sqrt(tree[i].minn))==(tree[i].maxx-(long long)sqrt(tree[i].maxx))){
            long long u=tree[i].minn-(long long)sqrt(tree[i].minn);
            tree[i].lz+=u;
            tree[i].sum-=(tree[i].r-tree[i].l+1)*u;
            tree[i].minn-=u;
            tree[i].maxx-=u;
                //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
            return ;
        }
        if(tree[i].r<l || tree[i].l>r)  return ;
        push_down(i);
        if(tree[i*2].r>=l)  Sqrt(i*2,l,r);
        if(tree[i*2+1].l<=r)  Sqrt(i*2+1,l,r);
        tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
        tree[i].minn=min(tree[i*2].minn,tree[i*2+1].minn);
        tree[i].maxx=max(tree[i*2].maxx,tree[i*2+1].maxx);
        //cout<<"i"<<i<<" "<<tree[i].sum<<endl;
        return ;
    }
    inline long long search(int i,int l,int r){
        if(tree[i].l>=l && tree[i].r<=r)
            return tree[i].sum;
        if(tree[i].r<l || tree[i].l>r)  return 0;
        push_down(i);
        long long s=0;
        if(tree[i*2].r>=l)  s+=search(i*2,l,r);
        if(tree[i*2+1].l<=r)  s+=search(i*2+1,l,r);
        return s;
    }
    int main(){
        in(n);
        REP(i,1,n)  in(input[i]);
        build(1,1,n);
        in(m);
        int a,b,c;
        REP(i,1,m){
            in(a);in(b);in(c);
            if(a==1)
                printf("%lld\n",search(1,b,c));
            if(a==2){
                Sqrt(1,b,c);
                //for(int i=1;i<=7;i++)
                //    cout<<tree[i].sum<<" ";
               // cout<<endl;
            }
        }
    }
    

    这一篇文章讲解的非常详细易懂,所以存下来用来复习。
    对原作者的图进行了重画,更加清晰,对排版也做了优化。
    后面的模板代码也用的是我自己AC的代码。
    注:如果您通过本文,有(qi)用(guai)的知识增加了,请您点个赞再离开,如果不嫌弃的话,点个关注再走吧 ! 当然,也欢迎在讨论区指出此文的不足处,作者会及时对文章加以修正 !

    展开全文
  • 线段树

    2019-08-31 14:47:51
    线段树线段树区间修改(加)+ 区间查询区间修改(加+乘)+区间查询静态区间第K小参考博客 线段树 线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。 ...

    线段树

    线段树是一种二叉搜索树,与区间树相似,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
    使用线段树可以快速的查找某一个节点在若干条线段中出现的次数,时间复杂度为O(logN)。而未优化的空间复杂度为2N,实际应用时一般还要开4N的数组以免越界,因此有时需要离散化让空间压缩。

    区间修改(加)+ 区间查询

    #include<cstdio>
    const int MAXN=1e5+5;
    typedef long long ll;
    
    /*
    * 利用线段树的完成下面操作:
    * 1.区间修改
    * 2.区间查询
    */
    
    
    ll n,m,a[MAXN],ans[MAXN<<2],tag[MAXN<<2];
    /*
    a:读入的原数组
    ans:构造的线段树
    tag:懒标记 使区间更新的复杂度就达到O(logn)
    标记的含义:本区间已经被更新过了,但是子区间却没有被更新过,
    被更新的信息是什么(区间求和只用记录有没有被访问过,而区间加减乘除等多种操作的问题则要记录进行的是哪一种操作)
    相对标记指的是可以共存的标记,且打标记的顺序与答案无关,即标记可以叠加。 比如说给一段区间中的所有数字都+a,
    我们就可以把标记叠加一下,比如上一次打了一个+1的标记,这一次要给这一段区间+2,那么就把+1的标记变成+3。
    绝对标记是指不可以共存的标记,每一次都要先把标记下传,再给当前节点打上新的标记。这些标记不能改变次序,
    否则会出错。 比如说给一段区间的数字重新赋值,或是给一段区间进行多种操作。
    */ 
    
    
    inline ll ls(ll x)
    {
        return x<<1;
    }//寻找左孩子(2*x)
    
    inline ll rs(ll x)
    {
        return x<<1|1;//位运算的效率高
    }//寻找右孩子(2*x+1)
    
    
    inline void push_up(ll p)
    {
        ans[p]=ans[ls(p)]+ans[rs(p)];
    }//维护父子节点之间的逻辑关系
    // ans[p]=max(ans[ls(p)],ans[rs(p))维护区间最大值
    // ans[p]=min(ans[ls(p)],ans[rs(p))维护区间最小值
    
    void build(ll p,ll l,ll r)
    {
        // p当前节点的编号
        //l,r 当前区间的左边界,右边界
        tag[p]=0;
        if(l==r){ans[p]=a[l];return ;}//叶子结点
        ll mid=(l+r)>>1;//区间分半
        build(ls(p),l,mid);
        build(rs(p),mid+1,r);
        push_up(p);//递归实际意义是先向底层递归,然后从底层向上回溯
        //先去整合子节点的信息,再向它们的祖先回溯整合之后的信息
    } //建树
    
    inline void f(ll p,ll l,ll r,ll k)
    {
        tag[p]=tag[p]+k;
        ans[p]=ans[p]+k*(r-l+1);
        //由于是这个区间统一改变,所以ans数组要加元素个数次啦 
    }//f函数的唯一目的,就是记录当前节点所代表的区间 
    
    inline void push_down(ll p,ll l,ll r)
    {
        ll mid=(l+r)>>1;
        f(ls(p),l,mid,tag[p]);
        f(rs(p),mid+1,r,tag[p]);
        tag[p]=0;
        //每次更新两个儿子节点。以此不断向下传递 
    }
    
    inline void update(ll nl,ll nr,ll l,ll r,ll p,ll k)
    {
        //nl,nr为要修改的区间[nl,nr]
        //l,r,p为当前节点所存储的区间[l,r]以及节点的编号 p
        //k 区间[nl,nr]增加k
        if(nl<=l&&r<=nr)
        {
            ans[p]+=k*(r-l+1);
            tag[p]+=k;
            //懒惰标记叠加
            return ;
        }
        push_down(p,l,r);
        //回溯之前(也可以说是下一次递归之前,因为没有递归就没有回溯) 
        //由于是在回溯之前不断向下传递,所以自然每个节点都可以更新到 
        ll mid=(l+r)>>1;
        if(nl<=mid)update(nl,nr,l,mid,ls(p),k);
        if(nr>mid) update(nl,nr,mid+1,r,rs(p),k);
        push_up(p);
    }
    
    ll query(ll ql,ll qr,ll l,ll r,ll p)
    {
        //查询区间[ql,qr]的区间和
        ll res=0;
        if(ql<=l&&r<=qr)return ans[p];
        ll mid=(l+r)>>1;
        push_down(p,l,r);
        if(ql<=mid)res+=query(ql,qr,l,mid,ls(p));
        if(qr>mid) res+=query(ql,qr,mid+1,r,rs(p));
        return res;
    }
    
    int main()
    {
        ll op,l,r,d;
        scanf("%d%d",&n,&m);
        for(int i=1;i<=n;++i)scanf("%lld",a+i);
        build(1,1,n);
        while(m--)
        {
            scanf("%lld%lld%lld",&op,&l,&r);
            if(op==1){
                scanf("%lld",&d);
                update(l,r,1,n,1,d);//修改区间[l,r] ,区间内的数相加d
            }else  printf("%lld\n",query(l,r,1,n,1));//查询区间[l,r]的和
        }
        return 0;
    }
    

    区间修改(加+乘)+区间查询

    #include<cstdio>
    const int maxn=1e5+5;
    typedef long long ll;
    
    /*
    * 利用线段树完成区间修改(加+乘)+区间查询
    1.将某区间[x,y]每一个数乘上k 
    2.将某区间[x,y]每一个数加上k
    3.求出某区间[x,y]每一个数的和
    */
    
    ll a[maxn],tree[maxn*4],mul[maxn*4],add[maxn*4],n,m,mod;
    //a:读入的原始数据
    //tree:线段树节点值
    //mul:乘法懒标记
    //add:加法懒标记
    //为了区分两种标记,add初始为0(加0不影响原来的值),mul初始化为1(乘以1不影响原来的值)
    
    inline void maintain(ll p){
        tree[p]=(tree[p<<1]+tree[p<<1|1])%mod;
    }//维护父子节点之间的逻辑关系
    
    void build(ll p,ll l,ll r){
        mul[p]=1;
        add[p]=0;
        if (l==r){
            tree[p]=a[l];
            return ;
        }
        ll mid=(l+r)>>1;//区间分解
        build(p<<1,l,mid);
        build(p<<1|1,mid+1,r);
        //注意p<<1|1 等价于p*2+1,或(p<<1)+1,<<的优先级低,位运算的效率高
        maintain(p);
    }//建树
    
    void ADD(ll p,ll l,ll r,ll mulk,ll sumk){
        tree[p]=(tree[p]*mulk+(r-l+1)*sumk)%mod;//修改节点
        add[p]=(add[p]*mulk+sumk)%mod;
        mul[p]=(mul[p]*mulk)%mod;
        //更新懒标记
        return ;
    }//执行区间修改的时候节点
    
    void pushdown(ll p,ll l,ll r){
        ll mid=(l+r)>>1;
        ADD(p<<1,l,mid,mul[p],add[p]);
        ADD(p<<1|1,mid+1,r,mul[p],add[p]);
        add[p]=0;
        mul[p]=1;
        return ;
    }//每次更新两个儿子节点。以此不断向下传递 
    
    void changemul(ll p,ll l,ll r,ll x,ll y,ll v){
        if (x<=l&&r<=y){
            ADD(p,l,r,v,0);
            return ;
        }
        pushdown(p,l,r);
        ll mid=(l+r)>>1;
        if (x<=mid) changemul(p<<1,l,mid,x,y,v);//我不是注释:看是否还有包含的交集,下同理
        if (mid<y) changemul(p<<1|1,mid+1,r,x,y,v);
        maintain(p);
    }
    
    void changesum(ll p,ll l,ll r,ll x,ll y,ll v){
        //区间修改,在[x,y]每个数加上v
        //当前区间[l,r],根节点p
        if (x<=l&&r<=y){
            ADD(p,l,r,1,v);
            return ;
        }//[l,r]属于[x,y]
        pushdown(p,l,r);//往下递归
        ll mid=(l+r)>>1;
        if (x<=mid) changesum(p<<1,l,mid,x,y,v);
        if (mid<y) changesum(p<<1|1,mid+1,r,x,y,v);
        maintain(p);
    }
    
    ll query(ll p,ll l,ll r,ll x,ll y){
        //求解区间[x,y]的值
        //当前区间[l,r],根节点p
        if (x<=l&&r<=y) return tree[p] ;//[l,r]属于[x,y]
        pushdown(p,l,r);//往下递归
        ll mid=(l+r)>>1,res=0;
        if (x<=mid) res+=query(p<<1,l,mid,x,y);
        if (mid<y) res+=query(p<<1|1,mid+1,r,x,y);
        return res%mod;
    }//区间询问
    
    int main(){
        scanf("%lld%lld%lld",&n,&m,&mod);
        for (ll i=1;i<=n;i++)scanf("%lld",&a[i]);
        build(1,1,n);
        ll op,x,y,k;
        for (ll i=1;i<=m;i++){
            scanf("%lld%lld%lld",&op,&x,&y);
            if (op==1){
                scanf("%lld",&k);
                changemul(1,1,n,x,y,k);
            }else if (op==2){
                scanf("%lld",&k);
                changesum(1,1,n,x,y,k);
            }else if (op==3)printf("%lld\n",query(1,1,n,x,y));
        }
        return 0;
    } 
    

    静态区间第K小

    #include <cstdio>
    #include<algorithm>
    const int maxn = 2e5+5;
    
    /*
    * 利用可持久化线段树(主席树)静态查询区间第k小
    * 主席树是利用函数式的编程思想使得线段树支持查询历史版本,
    * 同时充分利用他们之间的共同数据来减少时间和内存消耗的数据结构
    * 主席树的每个节点保存的是一颗线段树,维护的区间信息,
    * 结构相同,因此具有可加减性
    * 静态主席树的一些特点:
    1.建树时首先需要建一棵空的线段树,即最原始的主席树,
    此时主席树只含有一个空的节点,之后依次对原序列按某种顺序更新,
    就是将原序列加入到相应的位置
    2.主席树是一种特殊的线段树集,它包含了所有线段树的优势,
    并且可以保存历史状态,主席树查找和更新的时空复杂度都为O(nlogn)
    且总空间复杂度为O(nlogn+nlogn)前者为空树的复杂度,
    后者为更新n次的空间复杂度,缺点是空间损耗巨大
    3.主席树可以处理区间[L,R]中介于[x,y]的值的问题
    4.若增加空间垃圾回收则可以使空间复杂度降低一个log
    */
    
    int node_cnt, n, m;
    // node_cnt 记录节点的个数
    int sum[maxn<<5], rt[maxn], lc[maxn<<5], rc[maxn<<5];//线段树相关
    int a[maxn], b[maxn];//原序列和离散化序列
    int p;//修改点
    
    void build(int &t, int l, int r)
    {
        t = ++node_cnt;
        if(l == r) return;
        int mid = (l + r) >> 1;
        build(lc[t], l, mid);
        build(rc[t], mid+1, r);
    }//建一个全0的线段树,称作基础主席树;
    
    int update(int o, int l, int r)
    {
        //节点o表示区间[l,r],修改点为p,
        int oo = ++node_cnt;
        lc[oo] = lc[o]; rc[oo] = rc[o]; sum[oo] = sum[o] + 1;
        if(l == r) return oo;
        int mid = (l + r) >> 1;
        if(p <= mid) lc[oo] = update(lc[oo], l, mid);
        else rc[oo] = update(rc[oo], mid+1, r);
        return oo;
    }
    
    int query(int u, int v, int l, int r, int k)
    {
        // 查询线段树[u,v]区间的第k大
        int ans, mid = ((l + r) >> 1), x = sum[lc[v]] - sum[lc[u]];
        if(l == r) return l;
        if(x >= k) ans = query(lc[u], lc[v], l, mid, k);
        else ans = query(rc[u], rc[v], mid+1, r, k-x);
        return ans;
    }
    
    int main()
    {
        int l, r, k, q, ans;
        scanf("%d%d", &n, &m);
        for(int i = 1; i <= n; ++i)scanf("%d", &a[i]), b[i] = a[i];
        std::sort(b+1, b+n+1);
        q = std::unique(b+1, b+n+1) - b - 1;//去重,离散化
        build(rt[0], 1, q);
        for( int i = 1; i <= n; ++i){
            p = std::lower_bound(b+1, b+q+1, a[i])-b;//可以视为查找最小下标的匹配值,核心算法是二分查找
            rt[i] = update(rt[i-1], 1, q);
        }
        while(m--){
            scanf("%d%d%d", &l, &r, &k);
            ans = query(rt[l-1], rt[r], 1, q, k);
            printf("%d\n", b[ans]);
        }
        return 0;
    }
    //动态主席树就是在静态主席树基础上增加了一批用树状数组维护的线段树
    //利用差分完成
    

    参考博客

    P3372 【模板】线段树 1 题解
    P3373 【模板】线段树 2
    P3834 【模板】可持久化线段树 1(主席树) 题解
    线段树详解
    线段树的原理与模板
    线段树详解 (原理,实现与应用)
    poj 2104 K-th Number 主席树+超级详细解释

    展开全文
  • 线段树 转载请注明出处,谢谢!http://blog.csdn.net/metalseed/article/details/8039326  一:线段树基本概念 1:概述 线段树,类似区间树,是一个完全二叉树,它在各个节点保存一条线段(数组中的一段子...

    线段树


    转载请注明出处,谢谢!http://blog.csdn.net/metalseed/article/details/8039326 


    一:线段树基本概念

    1:概述

    线段树,类似区间树,是一个完全二叉树,它在各个节点保存一条线段(数组中的一段子数组),主要用于高效解决连续区间的动态查询问题,由于二叉结构的特性,它基本能保持每个操作的复杂度为O(lgN)!

    性质:父亲的区间是[a,b],(c=(a+b)/2)左儿子的区间是[a,c],右儿子的区间是[c+1,b],线段树需要的空间为数组大小的四倍


    2:基本操作(demo用的是查询区间最小值)

    线段树的主要操作有:

    (1):线段树的构造 void build(int node, int begin, int end);

    主要思想是递归构造,如果当前节点记录的区间只有一个值,则直接赋值,否则递归构造左右子树,最后回溯的时候给当前节点赋值

    [cpp]  view plain  copy
     print ?
    1. #include <iostream>  
    2. using namespace std;  
    3.   
    4. const int maxind = 256;  
    5. int segTree[maxind * 4 + 10];  
    6. int array[maxind];   
    7. /* 构造函数,得到线段树 */  
    8. void build(int node, int begin, int end)    
    9. {    
    10.     if (begin == end)    
    11.         segTree[node] = array[begin]; /* 只有一个元素,节点记录该单元素 */  
    12.     else    
    13.     {     
    14.         /* 递归构造左右子树 */   
    15.         build(2*node, begin, (begin+end)/2);    
    16.         build(2*node+1, (begin+end)/2+1, end);   
    17.            
    18.         /* 回溯时得到当前node节点的线段信息 */    
    19.         if (segTree[2 * node] <= segTree[2 * node + 1])    
    20.             segTree[node] = segTree[2 * node];    
    21.         else    
    22.             segTree[node] = segTree[2 * node + 1];    
    23.     }    
    24. }  
    25.   
    26. int main()  
    27. {  
    28.     array[0] = 1, array[1] = 2,array[2] = 2, array[3] = 4, array[4] = 1, array[5] = 3;  
    29.     build(1, 0, 5);  
    30.     for(int i = 1; i<=20; ++i)  
    31.      cout<< "seg"<< i << "=" <<segTree[i] <<endl;  
    32.     return 0;  
    33. }   
     此build构造成的树如图:

    (2):区间查询int query(int node, int begin, int end, int left, int right);

    (其中node为当前查询节点,begin,end为当前节点存储的区间,left,right为此次query所要查询的区间)

    主要思想是把所要查询的区间[a,b]划分为线段树上的节点,然后将这些节点代表的区间合并起来得到所需信息

    比如前面一个图中所示的树,如果询问区间是[0,2],或者询问的区间是[3,3],不难直接找到对应的节点回答这一问题。但并不是所有的提问都这么容易回答,比如[0,3],就没有哪一个节点记录了这个区间的最小值。当然,解决方法也不难找到:把[0,2][3,3]两个区间(它们在整数意义上是相连的两个区间)的最小值合并起来,也就是求这两个最小值的最小值,就能求出[0,3]范围的最小值。同理,对于其他询问的区间,也都可以找到若干个相连的区间,合并后可以得到询问的区间。

    [cpp]  view plain  copy
     print ?
    1. int query(int node, int begin, int end, int left, int right)    
    2. {   
    3.     int p1, p2;    
    4.     
    5.     /*  查询区间和要求的区间没有交集  */  
    6.     if (left > end || right < begin)    
    7.         return -1;    
    8.     
    9.     /*  if the current interval is included in  */    
    10.     /*  the query interval return segTree[node]  */  
    11.     if (begin >= left && end <= right)    
    12.         return segTree[node];    
    13.     
    14.     /*  compute the minimum position in the  */  
    15.     /*  left and right part of the interval  */   
    16.     p1 = query(2 * node, begin, (begin + end) / 2, left, right);   
    17.     p2 = query(2 * node + 1, (begin + end) / 2 + 1, end, left, right);    
    18.     
    19.     /*  return the expect value  */   
    20.     if (p1 == -1)    
    21.         return p2;    
    22.     if (p2 == -1)    
    23.         return p1;    
    24.     if (p1 <= p2)    
    25.         return  p1;    
    26.     return  p2;      
    27. }   

    可见,这样的过程一定选出了尽量少的区间,它们相连后正好涵盖了整个[left,right],没有重复也没有遗漏。同时,考虑到线段树上每层的节点最多会被选取2个,一共选取的节点数也是O(log n)的,因此查询的时间复杂度也是O(log n)。

    线段树并不适合所有区间查询情况,它的使用条件是“相邻的区间的信息可以被合并成两个区间的并区间的信息”。即问题是可以被分解解决的。



    (3):区间或节点的更新 及 线段树的动态维护update (这是线段树核心价值所在,节点中的标记域可以解决N多种问题)

    动态维护需要用到标记域,延迟标记等。

    a:单节点更新

    [cpp]  view plain  copy
     print ?
    1. void Updata(int node, int begin, int end, int ind, int add)/*单节点更新*/    
    2. {    
    3.     
    4.     if( begin == end )    
    5.     {    
    6.         segTree[node] += add;    
    7.         return ;    
    8.     }    
    9.     int m = ( left + right ) >> 1;    
    10.     if(ind <= m)    
    11.         Updata(node * 2,left, m, ind, add);    
    12.     else    
    13.         Updata(node * 2 + 1, m + 1, right, ind, add);    
    14.     /*回溯更新父节点*/    
    15.     segTree[node] = min(segTree[node * 2], segTree[node * 2 + 1]);     
    16.          
    17. }   

    b:区间更新(线段树中最有用的)

    需要用到延迟标记,每个结点新增加一个标记,记录这个结点是否被进行了某种修改操作(这种修改操作会影响其子结点)。对于任意区间的修改,我们先按照查询的方式将其划分成线段树中的结点,然后修改这些结点的信息,并给这些结点标上代表这种修改操作的标记。在修改和查询的时候,如果我们到了一个结点p,并且决定考虑其子结点,那么我们就要看看结点p有没有标记,如果有,就要按照标记修改其子结点的信息,并且给子结点都标上相同的标记,同时消掉p的标记。(优点在于,不用将区间内的所有值都暴力更新,大大提高效率,因此区间更新是最优用的操作)

    void Change来自dongxicheng.org

    [cpp]  view plain  copy
     print ?
    1. void Change(node *p, int a, int b) /* 当前考察结点为p,修改区间为(a,b]*/  
    2.    
    3. {  
    4.    
    5.   if (a <= p->Left && p->Right <= b)  
    6.    
    7.   /* 如果当前结点的区间包含在修改区间内*/  
    8.    
    9.   {  
    10.    
    11.      ...... /* 修改当前结点的信息,并标上标记*/  
    12.    
    13.      return;  
    14.    
    15.   }  
    16.    
    17.   Push_Down(p); /* 把当前结点的标记向下传递*/  
    18.    
    19.   int mid = (p->Left + p->Right) / 2; /* 计算左右子结点的分隔点 
    20.   
    21.   if (a < mid) Change(p->Lch, a, b); /* 和左孩子有交集,考察左子结点*/  
    22.    
    23.   if (b > mid) Change(p->Rch, a, b); /* 和右孩子有交集,考察右子结点*/  
    24.    
    25.   Update(p); /* 维护当前结点的信息(因为其子结点的信息可能有更改)*/  
    26.    
    27. }  



    3:主要应用

    (1):区间最值查询问题 (见模板1)

    (2):连续区间修改或者单节点更新的动态查询问题 (见模板2)

    (3):多维空间的动态查询 (见模板3)


    二:典型模板

    模板1:

    RMQ,查询区间最值下标---min

    [cpp]  view plain  copy
     print ?
    1. #include<iostream>    
    2.   
    3. using namespace std;    
    4.     
    5. #define MAXN 100    
    6. #define MAXIND 256 //线段树节点个数    
    7.     
    8. //构建线段树,目的:得到M数组.    
    9. void build(int node, int b, int e, int M[], int A[])    
    10. {    
    11.     if (b == e)    
    12.         M[node] = b; //只有一个元素,只有一个下标    
    13.     else    
    14.     {     
    15.         build(2 * node, b, (b + e) / 2, M, A);    
    16.         build(2 * node + 1, (b + e) / 2 + 1, e, M, A);    
    17.   
    18.         if (A[M[2 * node]] <= A[M[2 * node + 1]])    
    19.             M[node] = M[2 * node];    
    20.         else    
    21.             M[node] = M[2 * node + 1];    
    22.     }    
    23. }    
    24.     
    25. //找出区间 [i, j] 上的最小值的索引    
    26. int query(int node, int b, int e, int M[], int A[], int i, int j)    
    27. {    
    28.     int p1, p2;    
    29.     
    30.     //查询区间和要求的区间没有交集    
    31.     if (i > e || j < b)    
    32.         return -1;    
    33.   
    34.     if (b >= i && e <= j)    
    35.         return M[node];    
    36.    
    37.     p1 = query(2 * node, b, (b + e) / 2, M, A, i, j);    
    38.     p2 = query(2 * node + 1, (b + e) / 2 + 1, e, M, A, i, j);    
    39.     
    40.     //return the position where the overall    
    41.     //minimum is    
    42.     if (p1 == -1)    
    43.         return M[node] = p2;    
    44.     if (p2 == -1)    
    45.         return M[node] = p1;    
    46.     if (A[p1] <= A[p2])    
    47.         return M[node] = p1;    
    48.     return M[node] = p2;    
    49.     
    50. }    
    51.     
    52.     
    53. int main()    
    54. {    
    55.     int M[MAXIND]; //下标1起才有意义,否则不是二叉树,保存下标编号节点对应区间最小值的下标.    
    56.     memset(M,-1,sizeof(M));    
    57.     int a[]={3,4,5,7,2,1,0,3,4,5};    
    58.     build(1, 0, sizeof(a)/sizeof(a[0])-1, M, a);    
    59.     cout<<query(1, 0, sizeof(a)/sizeof(a[0])-1, M, a, 0, 5)<<endl;    
    60.     return 0;    
    61. }    



    模板2:

    连续区间修改或者单节点更新的动态查询问题 (此模板查询区间和)

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>    
    2. #include <algorithm>    
    3. using namespace std;    
    4.      
    5. #define lson l , m , rt << 1    
    6. #define rson m + 1 , r , rt << 1 | 1   
    7. #define root 1 , N , 1   
    8. #define LL long long    
    9. const int maxn = 111111;    
    10. LL add[maxn<<2];    
    11. LL sum[maxn<<2];    
    12. void PushUp(int rt) {    
    13.     sum[rt] = sum[rt<<1] + sum[rt<<1|1];    
    14. }    
    15. void PushDown(int rt,int m) {    
    16.     if (add[rt]) {    
    17.         add[rt<<1] += add[rt];    
    18.         add[rt<<1|1] += add[rt];    
    19.         sum[rt<<1] += add[rt] * (m - (m >> 1));    
    20.         sum[rt<<1|1] += add[rt] * (m >> 1);    
    21.         add[rt] = 0;    
    22.     }    
    23. }    
    24. void build(int l,int r,int rt) {    
    25.     add[rt] = 0;    
    26.     if (l == r) {    
    27.         scanf("%lld",&sum[rt]);    
    28.         return ;    
    29.     }    
    30.     int m = (l + r) >> 1;    
    31.     build(lson);    
    32.     build(rson);    
    33.     PushUp(rt);    
    34. }    
    35. void update(int L,int R,int c,int l,int r,int rt) {    
    36.     if (L <= l && r <= R) {    
    37.         add[rt] += c;    
    38.         sum[rt] += (LL)c * (r - l + 1);    
    39.         return ;    
    40.     }    
    41.     PushDown(rt , r - l + 1);    
    42.     int m = (l + r) >> 1;    
    43.     if (L <= m) update(L , R , c , lson);    
    44.     if (m < R) update(L , R , c , rson);    
    45.     PushUp(rt);    
    46. }    
    47. LL query(int L,int R,int l,int r,int rt) {    
    48.     if (L <= l && r <= R) {    
    49.         return sum[rt];    
    50.     }    
    51.     PushDown(rt , r - l + 1);    
    52.     int m = (l + r) >> 1;    
    53.     LL ret = 0;    
    54.     if (L <= m) ret += query(L , R , lson);    
    55.     if (m < R) ret += query(L , R , rson);    
    56.     return ret;    
    57. }    
    58. int main() {    
    59.     int N , Q;    
    60.     scanf("%d%d",&N,&Q);    
    61.     build(root);    
    62.     while (Q --) {    
    63.         char op[2];    
    64.         int a , b , c;    
    65.         scanf("%s",op);    
    66.         if (op[0] == 'Q') {    
    67.             scanf("%d%d",&a,&b);    
    68.             printf("%lld\n",query(a , b ,root));    
    69.         } else {    
    70.             scanf("%d%d%d",&a,&b,&c);    
    71.             update(a , b , c , root);    
    72.         }    
    73.     }    
    74.     return 0;    
    75. }    


    模板3:

    多维空间的动态查询



    三:练习题目

    下面是hh线段树代码,典型练习哇~

    在代码前先介绍一些我的线段树风格:

    • maxn是题目给的最大区间,而节点数要开4倍,确切的来说节点数要开大于maxn的最小2x的两倍
    • lson和rson分辨表示结点的左儿子和右儿子,由于每次传参数的时候都固定是这几个变量,所以可以用预定于比较方便的表示
    • 以前的写法是另外开两个个数组记录每个结点所表示的区间,其实这个区间不必保存,一边算一边传下去就行,只需要写函数的时候多两个参数,结合lson和rson的预定义可以很方便
    • PushUP(int rt)是把当前结点的信息更新到父结点
    • PushDown(int rt)是把当前结点的信息更新给儿子结点
    • rt表示当前子树的根(root),也就是当前所在的结点

    整理这些题目后我觉得线段树的题目整体上可以分成以下四个部分:



    单点更新:最最基础的线段树,只更新叶子节点,然后把信息用PushUP(int r)这个函数更新上来


    • hdu1166 敌兵布阵
    • 题意:O(-1)
    • 思路:O(-1)
      线段树功能:update:单点增减 query:区间求和

    code:

    [cpp]  view plain  copy
     print ?
    1. #include<cstring>  
    2. #include<iostream>  
    3.   
    4. #define M 50005  
    5. #define lson l,m,rt<<1  
    6. #define rson m+1,r,rt<<1|1  
    7. /*left,right,root,middle*/  
    8.   
    9. int sum[M<<2];  
    10.   
    11. inline void PushPlus(int rt)  
    12. {  
    13.     sum[rt] = sum[rt<<1] + sum[rt<<1|1];  
    14. }  
    15.   
    16. void Build(int l, int r, int rt)  
    17. {  
    18.     if(l == r)  
    19.     {  
    20.         scanf("%d", &sum[rt]);  
    21.         return ;  
    22.     }  
    23.     int m = ( l + r )>>1;  
    24.   
    25.     Build(lson);  
    26.     Build(rson);  
    27.     PushPlus(rt);  
    28. }  
    29.   
    30. void Updata(int p, int add, int l, int r, int rt)  
    31. {  
    32.   
    33.     if( l == r )  
    34.     {  
    35.         sum[rt] += add;  
    36.         return ;  
    37.     }  
    38.     int m = ( l + r ) >> 1;  
    39.     if(p <= m)  
    40.         Updata(p, add, lson);  
    41.     else  
    42.         Updata(p, add, rson);  
    43.   
    44.     PushPlus(rt);  
    45. }  
    46.   
    47. int Query(int L,int R,int l,int r,int rt)  
    48. {  
    49.     if( L <= l && r <= R )  
    50.     {  
    51.         return sum[rt];  
    52.     }  
    53.     int m = ( l + r ) >> 1;  
    54.     int ans=0;  
    55.     if(L<=m )  
    56.         ans+=Query(L,R,lson);  
    57.     if(R>m)  
    58.         ans+=Query(L,R,rson);  
    59.   
    60.     return ans;  
    61. }  
    62. int main()  
    63. {     
    64.     int T, n, a, b;  
    65.     scanf("%d",&T);  
    66.     forint i = 1; i <= T; ++i )  
    67.     {  
    68.         printf("Case %d:\n",i);  
    69.         scanf("%d",&n);  
    70.         Build(1,n,1);  
    71.   
    72.         char op[10];  
    73.   
    74.         while( scanf("%s",op) &&op[0]!='E' )  
    75.         {  
    76.   
    77.             scanf("%d %d", &a, &b);  
    78.             if(op[0] == 'Q')  
    79.                 printf("%d\n",Query(a,b,1,n,1));  
    80.             else if(op[0] == 'S')  
    81.                 Updata(a,-b,1,n,1);  
    82.             else  
    83.                 Updata(a,b,1,n,1);  
    84.   
    85.         }  
    86.     }  
    87.     return 0;  
    88. }  

    hdu1754 I Hate It
    题意:O(-1)
    思路:O(-1)
    线段树功能:update:单点替换 query:区间最值

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <algorithm>  
    3. using namespace std;  
    4.    
    5. #define lson l , m , rt << 1  
    6. #define rson m + 1 , r , rt << 1 | 1  
    7. const int maxn = 222222;  
    8. int MAX[maxn<<2];  
    9. void PushUP(int rt) {  
    10.     MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);  
    11. }  
    12. void build(int l,int r,int rt) {  
    13.     if (l == r) {  
    14.         scanf("%d",&MAX[rt]);  
    15.         return ;  
    16.     }  
    17.     int m = (l + r) >> 1;  
    18.     build(lson);  
    19.     build(rson);  
    20.     PushUP(rt);  
    21. }  
    22. void update(int p,int sc,int l,int r,int rt) {  
    23.     if (l == r) {  
    24.         MAX[rt] = sc;  
    25.         return ;  
    26.     }  
    27.     int m = (l + r) >> 1;  
    28.     if (p <= m) update(p , sc , lson);  
    29.     else update(p , sc , rson);  
    30.     PushUP(rt);  
    31. }  
    32. int query(int L,int R,int l,int r,int rt) {  
    33.     if (L <= l && r <= R) {  
    34.         return MAX[rt];  
    35.     }  
    36.     int m = (l + r) >> 1;  
    37.     int ret = 0;  
    38.     if (L <= m) ret = max(ret , query(L , R , lson));  
    39.     if (R > m) ret = max(ret , query(L , R , rson));  
    40.     return ret;  
    41. }  
    42. int main() {  
    43.     int n , m;  
    44.     while (~scanf("%d%d",&n,&m)) {  
    45.         build(1 , n , 1);  
    46.         while (m --) {  
    47.             char op[2];  
    48.             int a , b;  
    49.             scanf("%s%d%d",op,&a,&b);  
    50.             if (op[0] == 'Q') printf("%d\n",query(a , b , 1 , n , 1));  
    51.             else update(a , b , 1 , n , 1);  
    52.         }  
    53.     }  
    54.     return 0;  
    55. }  

    hdu1394 Minimum Inversion Number
    题意:求Inversion后的最小逆序数
    思路:用O(nlogn)复杂度求出最初逆序数后,就可以用O(1)的复杂度分别递推出其他解
    线段树功能:update:单点增减 query:区间求和

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <algorithm>  
    3. using namespace std;  
    4.    
    5. #define lson l , m , rt << 1  
    6. #define rson m + 1 , r , rt << 1 | 1  
    7. const int maxn = 5555;  
    8. int sum[maxn<<2];  
    9. void PushUP(int rt) {  
    10.     sum[rt] = sum[rt<<1] + sum[rt<<1|1];  
    11. }  
    12. void build(int l,int r,int rt) {  
    13.     sum[rt] = 0;  
    14.     if (l == r) return ;  
    15.     int m = (l + r) >> 1;  
    16.     build(lson);  
    17.     build(rson);  
    18. }  
    19. void update(int p,int l,int r,int rt) {  
    20.     if (l == r) {  
    21.         sum[rt] ++;  
    22.         return ;  
    23.     }  
    24.     int m = (l + r) >> 1;  
    25.     if (p <= m) update(p , lson);  
    26.     else update(p , rson);  
    27.     PushUP(rt);  
    28. }  
    29. int query(int L,int R,int l,int r,int rt) {  
    30.     if (L <= l && r <= R) {  
    31.         return sum[rt];  
    32.     }  
    33.     int m = (l + r) >> 1;  
    34.     int ret = 0;  
    35.     if (L <= m) ret += query(L , R , lson);  
    36.     if (R > m) ret += query(L , R , rson);  
    37.     return ret;  
    38. }  
    39. int x[maxn];  
    40. int main() {  
    41.     int n;  
    42.     while (~scanf("%d",&n)) {  
    43.         build(0 , n - 1 , 1);  
    44.         int sum = 0;  
    45.         for (int i = 0 ; i < n ; i ++) {  
    46.             scanf("%d",&x[i]);  
    47.             sum += query(x[i] , n - 1 , 0 , n - 1 , 1);  
    48.             update(x[i] , 0 , n - 1 , 1);  
    49.         }  
    50.         int ret = sum;  
    51.         for (int i = 0 ; i < n ; i ++) {  
    52.             sum += n - x[i] - x[i] - 1;  
    53.             ret = min(ret , sum);  
    54.         }  
    55.         printf("%d\n",ret);  
    56.     }  
    57.     return 0;  
    58. }  

    hdu2795 Billboard
    题意:h*w的木板,放进一些1*L的物品,求每次放空间能容纳且最上边的位子
    思路:每次找到最大值的位子,然后减去L
    线段树功能:query:区间求最大值的位子(直接把update的操作在query里做了)

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <algorithm>  
    3. using namespace std;  
    4.    
    5. #define lson l , m , rt << 1  
    6. #define rson m + 1 , r , rt << 1 | 1  
    7. const int maxn = 222222;  
    8. int h , w , n;  
    9. int MAX[maxn<<2];  
    10. void PushUP(int rt) {  
    11.     MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);  
    12. }  
    13. void build(int l,int r,int rt) {  
    14.     MAX[rt] = w;  
    15.     if (l == r) return ;  
    16.     int m = (l + r) >> 1;  
    17.     build(lson);  
    18.     build(rson);  
    19. }  
    20. int query(int x,int l,int r,int rt) {  
    21.     if (l == r) {  
    22.         MAX[rt] -= x;  
    23.         return l;  
    24.     }  
    25.     int m = (l + r) >> 1;  
    26.     int ret = (MAX[rt<<1] >= x) ? query(x , lson) : query(x , rson);  
    27.     PushUP(rt);  
    28.     return ret;  
    29. }  
    30. int main() {  
    31.     while (~scanf("%d%d%d",&h,&w,&n)) {  
    32.         if (h > n) h = n;  
    33.         build(1 , h , 1);  
    34.         while (n --) {  
    35.             int x;  
    36.             scanf("%d",&x);  
    37.             if (MAX[1] < x) puts("-1");  
    38.             else printf("%d\n",query(x , 1 , h , 1));  
    39.         }  
    40.     }  
    41.     return 0;  
    42. }  

    成段更新(通常这对初学者来说是一道坎),需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候

    hdu1698 Just a Hook
    题意:O(-1)
    思路:O(-1)
    线段树功能:update:成段替换 (由于只query一次总区间,所以可以直接输出1结点的信息)
    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <algorithm>  
    3. using namespace std;  
    4.    
    5. #define lson l , m , rt << 1  
    6. #define rson m + 1 , r , rt << 1 | 1  
    7. const int maxn = 111111;  
    8. int h , w , n;  
    9. int col[maxn<<2];  
    10. int sum[maxn<<2];  
    11. void PushUp(int rt) {  
    12.     sum[rt] = sum[rt<<1] + sum[rt<<1|1];  
    13. }  
    14. void PushDown(int rt,int m) {  
    15.     if (col[rt]) {  
    16.         col[rt<<1] = col[rt<<1|1] = col[rt];  
    17.         sum[rt<<1] = (m - (m >> 1)) * col[rt];  
    18.         sum[rt<<1|1] = (m >> 1) * col[rt];  
    19.         col[rt] = 0;  
    20.     }  
    21. }  
    22. void build(int l,int r,int rt) {  
    23.     col[rt] = 0;  
    24.     sum[rt] = 1;  
    25.     if (l == r) return ;  
    26.     int m = (l + r) >> 1;  
    27.     build(lson);  
    28.     build(rson);  
    29.     PushUp(rt);  
    30. }  
    31. void update(int L,int R,int c,int l,int r,int rt) {  
    32.     if (L <= l && r <= R) {  
    33.         col[rt] = c;  
    34.         sum[rt] = c * (r - l + 1);  
    35.         return ;  
    36.     }  
    37.     PushDown(rt , r - l + 1);  
    38.     int m = (l + r) >> 1;  
    39.     if (L <= m) update(L , R , c , lson);  
    40.     if (R > m) update(L , R , c , rson);  
    41.     PushUp(rt);  
    42. }  
    43. int main() {  
    44.     int T , n , m;  
    45.     scanf("%d",&T);  
    46.     for (int cas = 1 ; cas <= T ; cas ++) {  
    47.         scanf("%d%d",&n,&m);  
    48.         build(1 , n , 1);  
    49.         while (m --) {  
    50.             int a , b , c;  
    51.             scanf("%d%d%d",&a,&b,&c);  
    52.             update(a , b , c , 1 , n , 1);  
    53.         }  
    54.         printf("Case %d: The total value of the hook is %d.\n",cas , sum[1]);  
    55.     }  
    56.     return 0;  
    57. }  

    poj3468 A Simple Problem with Integers
    题意:O(-1)
    思路:O(-1)
    线段树功能:update:成段增减 query:区间求和

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <algorithm>  
    3. using namespace std;  
    4.    
    5. #define lson l , m , rt << 1  
    6. #define rson m + 1 , r , rt << 1 | 1  
    7. #define LL long long  
    8. const int maxn = 111111;  
    9. LL add[maxn<<2];  
    10. LL sum[maxn<<2];  
    11. void PushUp(int rt) {  
    12.     sum[rt] = sum[rt<<1] + sum[rt<<1|1];  
    13. }  
    14. void PushDown(int rt,int m) {  
    15.     if (add[rt]) {  
    16.         add[rt<<1] += add[rt];  
    17.         add[rt<<1|1] += add[rt];  
    18.         sum[rt<<1] += add[rt] * (m - (m >> 1));  
    19.         sum[rt<<1|1] += add[rt] * (m >> 1);  
    20.         add[rt] = 0;  
    21.     }  
    22. }  
    23. void build(int l,int r,int rt) {  
    24.     add[rt] = 0;  
    25.     if (l == r) {  
    26.         scanf("%lld",&sum[rt]);  
    27.         return ;  
    28.     }  
    29.     int m = (l + r) >> 1;  
    30.     build(lson);  
    31.     build(rson);  
    32.     PushUp(rt);  
    33. }  
    34. void update(int L,int R,int c,int l,int r,int rt) {  
    35.     if (L <= l && r <= R) {  
    36.         add[rt] += c;  
    37.         sum[rt] += (LL)c * (r - l + 1);  
    38.         return ;  
    39.     }  
    40.     PushDown(rt , r - l + 1);  
    41.     int m = (l + r) >> 1;  
    42.     if (L <= m) update(L , R , c , lson);  
    43.     if (m < R) update(L , R , c , rson);  
    44.     PushUp(rt);  
    45. }  
    46. LL query(int L,int R,int l,int r,int rt) {  
    47.     if (L <= l && r <= R) {  
    48.         return sum[rt];  
    49.     }  
    50.     PushDown(rt , r - l + 1);  
    51.     int m = (l + r) >> 1;  
    52.     LL ret = 0;  
    53.     if (L <= m) ret += query(L , R , lson);  
    54.     if (m < R) ret += query(L , R , rson);  
    55.     return ret;  
    56. }  
    57. int main() {  
    58.     int N , Q;  
    59.     scanf("%d%d",&N,&Q);  
    60.     build(1 , N , 1);  
    61.     while (Q --) {  
    62.         char op[2];  
    63.         int a , b , c;  
    64.         scanf("%s",op);  
    65.         if (op[0] == 'Q') {  
    66.             scanf("%d%d",&a,&b);  
    67.             printf("%lld\n",query(a , b , 1 , N , 1));  
    68.         } else {  
    69.             scanf("%d%d%d",&a,&b,&c);  
    70.             update(a , b , c , 1 , N , 1);  
    71.         }  
    72.     }  
    73.     return 0;  
    74. }  

    poj2528 Mayor’s posters
    题意:在墙上贴海报,海报可以互相覆盖,问最后可以看见几张海报
    思路:这题数据范围很大,直接搞超时+超内存,需要离散化:
    离散化简单的来说就是只取我们需要的值来用,比如说区间[1000,2000],[1990,2012] 我们用不到[-∞,999][1001,1989][1991,1999][2001,2011][2013,+∞]这些值,所以我只需要1000,1990,2000,2012就够了,将其分别映射到0,1,2,3,在于复杂度就大大的降下来了
    所以离散化要保存所有需要用到的值,排序后,分别映射到1~n,这样复杂度就会小很多很多
    而这题的难点在于每个数字其实表示的是一个单位长度(并非一个点),这样普通的离散化会造成许多错误(包括我以前的代码,poj这题数据奇弱)
    给出下面两个简单的例子应该能体现普通离散化的缺陷:
    例子一:1-10 1-4 5-10
    例子二:1-10 1-4 6-10
    普通离散化后都变成了[1,4][1,2][3,4]
    线段2覆盖了[1,2],线段3覆盖了[3,4],那么线段1是否被完全覆盖掉了呢?
    例子一是完全被覆盖掉了,而例子二没有被覆盖

    为了解决这种缺陷,我们可以在排序后的数组上加些处理,比如说[1,2,6,10]
    如果相邻数字间距大于1的话,在其中加上任意一个数字,比如加成[1,2,3,6,7,10],然后再做线段树就好了.
    线段树功能:update:成段替换 query:简单hash

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <cstring>  
    3. #include <algorithm>  
    4. using namespace std;  
    5. #define lson l , m , rt << 1  
    6. #define rson m + 1 , r , rt << 1 | 1  
    7.    
    8. const int maxn = 11111;  
    9. bool hash[maxn];  
    10. int li[maxn] , ri[maxn];  
    11. int X[maxn*3];  
    12. int col[maxn<<4];  
    13. int cnt;  
    14.    
    15. void PushDown(int rt) {  
    16.     if (col[rt] != -1) {  
    17.         col[rt<<1] = col[rt<<1|1] = col[rt];  
    18.         col[rt] = -1;  
    19.     }  
    20. }  
    21. void update(int L,int R,int c,int l,int r,int rt) {  
    22.     if (L <= l && r <= R) {  
    23.         col[rt] = c;  
    24.         return ;  
    25.     }  
    26.     PushDown(rt);  
    27.     int m = (l + r) >> 1;  
    28.     if (L <= m) update(L , R , c , lson);  
    29.     if (m < R) update(L , R , c , rson);  
    30. }  
    31. void query(int l,int r,int rt) {  
    32.     if (col[rt] != -1) {  
    33.         if (!hash[col[rt]]) cnt ++;  
    34.         hash[ col[rt] ] = true;  
    35.         return ;  
    36.     }  
    37.     if (l == r) return ;  
    38.     int m = (l + r) >> 1;  
    39.     query(lson);  
    40.     query(rson);  
    41. }  
    42. int Bin(int key,int n,int X[]) {  
    43.     int l = 0 , r = n - 1;  
    44.     while (l <= r) {  
    45.         int m = (l + r) >> 1;  
    46.         if (X[m] == key) return m;  
    47.         if (X[m] < key) l = m + 1;  
    48.         else r = m - 1;  
    49.     }  
    50.     return -1;  
    51. }  
    52. int main() {  
    53.     int T , n;  
    54.     scanf("%d",&T);  
    55.     while (T --) {  
    56.         scanf("%d",&n);  
    57.         int nn = 0;  
    58.         for (int i = 0 ; i < n ; i ++) {  
    59.             scanf("%d%d",&li[i] , &ri[i]);  
    60.             X[nn++] = li[i];  
    61.             X[nn++] = ri[i];  
    62.         }  
    63.         sort(X , X + nn);  
    64.         int m = 1;  
    65.         for (int i = 1 ; i < nn; i ++) {  
    66.             if (X[i] != X[i-1]) X[m ++] = X[i];  
    67.         }  
    68.         for (int i = m - 1 ; i > 0 ; i --) {  
    69.             if (X[i] != X[i-1] + 1) X[m ++] = X[i-1] + 1;  
    70.         }  
    71.         sort(X , X + m);  
    72.         memset(col , -1 , sizeof(col));  
    73.         for (int i = 0 ; i < n ; i ++) {  
    74.             int l = Bin(li[i] , m , X);  
    75.             int r = Bin(ri[i] , m , X);  
    76.             update(l , r , i , 0 , m , 1);  
    77.         }  
    78.         cnt = 0;  
    79.         memset(hash , false , sizeof(hash));  
    80.         query(0 , m , 1);  
    81.         printf("%d\n",cnt);  
    82.     }  
    83.     return 0;  
    84. }  

    poj3225 Help with Intervals
    题意:区间操作,交,并,补等
    思路:
    我们一个一个操作来分析:(用0和1表示是否包含区间,-1表示该区间内既有包含又有不包含)
    U:把区间[l,r]覆盖成1
    I:把[-∞,l)(r,∞]覆盖成0
    D:把区间[l,r]覆盖成0
    C:把[-∞,l)(r,∞]覆盖成0 , 且[l,r]区间0/1互换
    S:[l,r]区间0/1互换

    成段覆盖的操作很简单,比较特殊的就是区间0/1互换这个操作,我们可以称之为异或操作
    很明显我们可以知道这个性质:当一个区间被覆盖后,不管之前有没有异或标记都没有意义了
    所以当一个节点得到覆盖标记时把异或标记清空
    而当一个节点得到异或标记的时候,先判断覆盖标记,如果是0或1,直接改变一下覆盖标记,不然的话改变异或标记

    开区间闭区间只要数字乘以2就可以处理(偶数表示端点,奇数表示两端点间的区间)
    线段树功能:update:成段替换,区间异或 query:简单hash

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <cstring>  
    3. #include <cctype>  
    4. #include <algorithm>  
    5. using namespace std;  
    6. #define lson l , m , rt << 1  
    7. #define rson m + 1 , r , rt << 1 | 1  
    8.    
    9. const int maxn = 131072;  
    10. bool hash[maxn+1];  
    11. int cover[maxn<<2];  
    12. int XOR[maxn<<2];  
    13. void FXOR(int rt) {  
    14.     if (cover[rt] != -1) cover[rt] ^= 1;  
    15.     else XOR[rt] ^= 1;  
    16. }  
    17. void PushDown(int rt) {  
    18.     if (cover[rt] != -1) {  
    19.         cover[rt<<1] = cover[rt<<1|1] = cover[rt];  
    20.         XOR[rt<<1] = XOR[rt<<1|1] = 0;  
    21.         cover[rt] = -1;  
    22.     }  
    23.     if (XOR[rt]) {  
    24.         FXOR(rt<<1);  
    25.         FXOR(rt<<1|1);  
    26.         XOR[rt] = 0;  
    27.     }  
    28. }  
    29. void update(char op,int L,int R,int l,int r,int rt) {  
    30.     if (L <= l && r <= R) {  
    31.         if (op == 'U') {  
    32.             cover[rt] = 1;  
    33.             XOR[rt] = 0;  
    34.         } else if (op == 'D') {  
    35.             cover[rt] = 0;  
    36.             XOR[rt] = 0;  
    37.         } else if (op == 'C' || op == 'S') {  
    38.             FXOR(rt);  
    39.         }  
    40.         return ;  
    41.     }  
    42.     PushDown(rt);  
    43.     int m = (l + r) >> 1;  
    44.     if (L <= m) update(op , L , R , lson);  
    45.     else if (op == 'I' || op == 'C') {  
    46.         XOR[rt<<1] = cover[rt<<1] = 0;  
    47.     }  
    48.     if (m < R) update(op , L , R , rson);  
    49.     else if (op == 'I' || op == 'C') {  
    50.         XOR[rt<<1|1] = cover[rt<<1|1] = 0;  
    51.     }  
    52. }  
    53. void query(int l,int r,int rt) {  
    54.     if (cover[rt] == 1) {  
    55.         for (int it = l ; it <= r ; it ++) {  
    56.             hash[it] = true;  
    57.         }  
    58.         return ;  
    59.     } else if (cover[rt] == 0) return ;  
    60.     if (l == r) return ;  
    61.     PushDown(rt);  
    62.     int m = (l + r) >> 1;  
    63.     query(lson);  
    64.     query(rson);  
    65. }  
    66. int main() {  
    67.     cover[1] = XOR[1] = 0;  
    68.     char op , l , r;  
    69.     int a , b;  
    70.     while ( ~scanf("%c %c%d,%d%c\n",&op , &l , &a , &b , &r) ) {  
    71.         a <<= 1 , b <<= 1;  
    72.         if (l == '(') a ++;  
    73.         if (r == ')') b --;  
    74.         if (a > b) {  
    75.             if (op == 'C' || op == 'I') {  
    76.                 cover[1] = XOR[1] = 0;  
    77.             }  
    78.         } else update(op , a , b , 0 , maxn , 1);  
    79.     }  
    80.     query(0 , maxn , 1);  
    81.     bool flag = false;  
    82.     int s = -1 , e;  
    83.     for (int i = 0 ; i <= maxn ; i ++) {  
    84.         if (hash[i]) {  
    85.             if (s == -1) s = i;  
    86.             e = i;  
    87.         } else {  
    88.             if (s != -1) {  
    89.                 if (flag) printf(" ");  
    90.                 flag = true;  
    91.                 printf("%c%d,%d%c",s&1?'(':'[' , s>>1 , (e+1)>>1 , e&1?')':']');  
    92.                 s = -1;  
    93.             }  
    94.         }  
    95.     }  
    96.     if (!flag) printf("empty set");  
    97.     puts("");  
    98.     return 0;  
    99. }  
    练习
    poj1436 Horizontally Visible Segments
    poj2991 Crane
    Another LCIS
    Bracket Sequence

    区间合并

    这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并
    poj3667 Hotel
    题意:1 a:询问是不是有连续长度为a的空房间,有的话住进最左边
    2 a b:将[a,a+b-1]的房间清空
    思路:记录区间中最长的空房间
    线段树操作:update:区间替换 query:询问满足条件的最左断点
    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <cstring>  
    3. #include <cctype>  
    4. #include <algorithm>  
    5. using namespace std;  
    6. #define lson l , m , rt << 1  
    7. #define rson m + 1 , r , rt << 1 | 1  
    8.    
    9. const int maxn = 55555;  
    10. int lsum[maxn<<2] , rsum[maxn<<2] , msum[maxn<<2];  
    11. int cover[maxn<<2];  
    12.    
    13. void PushDown(int rt,int m) {  
    14.     if (cover[rt] != -1) {  
    15.         cover[rt<<1] = cover[rt<<1|1] = cover[rt];  
    16.         msum[rt<<1] = lsum[rt<<1] = rsum[rt<<1] = cover[rt] ? 0 : m - (m >> 1);  
    17.         msum[rt<<1|1] = lsum[rt<<1|1] = rsum[rt<<1|1] = cover[rt] ? 0 : (m >> 1);  
    18.         cover[rt] = -1;  
    19.     }  
    20. }  
    21. void PushUp(int rt,int m) {  
    22.     lsum[rt] = lsum[rt<<1];  
    23.     rsum[rt] = rsum[rt<<1|1];  
    24.     if (lsum[rt] == m - (m >> 1)) lsum[rt] += lsum[rt<<1|1];  
    25.     if (rsum[rt] == (m >> 1)) rsum[rt] += rsum[rt<<1];  
    26.     msum[rt] = max(lsum[rt<<1|1] + rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));  
    27. }  
    28. void build(int l,int r,int rt) {  
    29.     msum[rt] = lsum[rt] = rsum[rt] = r - l + 1;  
    30.     cover[rt] = -1;  
    31.     if (l == r) return ;  
    32.     int m = (l + r) >> 1;  
    33.     build(lson);  
    34.     build(rson);  
    35. }  
    36. void update(int L,int R,int c,int l,int r,int rt) {  
    37.     if (L <= l && r <= R) {  
    38.         msum[rt] = lsum[rt] = rsum[rt] = c ? 0 : r - l + 1;  
    39.         cover[rt] = c;  
    40.         return ;  
    41.     }  
    42.     PushDown(rt , r - l + 1);  
    43.     int m = (l + r) >> 1;  
    44.     if (L <= m) update(L , R , c , lson);  
    45.     if (m < R) update(L , R , c , rson);  
    46.     PushUp(rt , r - l + 1);  
    47. }  
    48. int query(int w,int l,int r,int rt) {  
    49.     if (l == r) return l;  
    50.     PushDown(rt , r - l + 1);  
    51.     int m = (l + r) >> 1;  
    52.     if (msum[rt<<1] >= w) return query(w , lson);  
    53.     else if (rsum[rt<<1] + lsum[rt<<1|1] >= w) return m - rsum[rt<<1] + 1;  
    54.     return query(w , rson);  
    55. }  
    56. int main() {  
    57.     int n , m;  
    58.     scanf("%d%d",&n,&m);  
    59.     build(1 , n , 1);  
    60.     while (m --) {  
    61.         int op , a , b;  
    62.         scanf("%d",&op);  
    63.         if (op == 1) {  
    64.             scanf("%d",&a);  
    65.             if (msum[1] < a) puts("0");  
    66.             else {  
    67.                 int p = query(a , 1 , n , 1);  
    68.                 printf("%d\n",p);  
    69.                 update(p , p + a - 1 , 1 , 1 , n , 1);  
    70.             }  
    71.         } else {  
    72.             scanf("%d%d",&a,&b);  
    73.             update(a , a + b - 1 , 0 , 1 , n , 1);  
    74.         }  
    75.     }  
    76.     return 0;  
    77. }  

    练习
    hdu3308 LCIS
    hdu3397 Sequence operation
    hdu2871 Memory Control
    hdu1540 Tunnel Warfare
    CF46-D Parking Lot

    扫描线

    这类题目需要将一些操作排序,然后从左到右用一根扫描线(当然是在我们脑子里)扫过去
    最典型的就是矩形面积并,周长并等题

    hdu1542 Atlantis
    题意:矩形面积并
    思路:浮点数先要离散化;然后把矩形分成两条边,上边和下边,对横轴建树,然后从下到上扫描上去,用cnt表示该区间下边比上边多几个,sum代表该区间内被覆盖的线段的长度总和
    这里线段树的一个结点并非是线段的一个端点,而是该端点和下一个端点间的线段,所以题目中r+1,r-1的地方可以自己好好的琢磨一下
    线段树操作:update:区间增减 query:直接取根节点的值
    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <cstring>  
    3. #include <cctype>  
    4. #include <algorithm>  
    5. using namespace std;  
    6. #define lson l , m , rt << 1  
    7. #define rson m + 1 , r , rt << 1 | 1  
    8.    
    9. const int maxn = 2222;  
    10. int cnt[maxn << 2];  
    11. double sum[maxn << 2];  
    12. double X[maxn];  
    13. struct Seg {  
    14.     double h , l , r;  
    15.     int s;  
    16.     Seg(){}  
    17.     Seg(double a,double b,double c,int d) : l(a) , r(b) , h(c) , s(d) {}  
    18.     bool operator < (const Seg &cmp) const {  
    19.         return h < cmp.h;  
    20.     }  
    21. }ss[maxn];  
    22. void PushUp(int rt,int l,int r) {  
    23.     if (cnt[rt]) sum[rt] = X[r+1] - X[l];  
    24.     else if (l == r) sum[rt] = 0;  
    25.     else sum[rt] = sum[rt<<1] + sum[rt<<1|1];  
    26. }  
    27. void update(int L,int R,int c,int l,int r,int rt) {  
    28.     if (L <= l && r <= R) {  
    29.         cnt[rt] += c;  
    30.         PushUp(rt , l , r);  
    31.         return ;  
    32.     }  
    33.     int m = (l + r) >> 1;  
    34.     if (L <= m) update(L , R , c , lson);  
    35.     if (m < R) update(L , R , c , rson);  
    36.     PushUp(rt , l , r);  
    37. }  
    38. int Bin(double key,int n,double X[]) {  
    39.     int l = 0 , r = n - 1;  
    40.     while (l <= r) {  
    41.         int m = (l + r) >> 1;  
    42.         if (X[m] == key) return m;  
    43.         if (X[m] < key) l = m + 1;  
    44.         else r = m - 1;  
    45.     }  
    46.     return -1;  
    47. }  
    48. int main() {  
    49.     int n , cas = 1;  
    50.     while (~scanf("%d",&n) && n) {  
    51.         int m = 0;  
    52.         while (n --) {  
    53.             double a , b , c , d;  
    54.             scanf("%lf%lf%lf%lf",&a,&b,&c,&d);  
    55.             X[m] = a;  
    56.             ss[m++] = Seg(a , c , b , 1);  
    57.             X[m] = c;  
    58.             ss[m++] = Seg(a , c , d , -1);  
    59.         }  
    60.         sort(X , X + m);  
    61.         sort(ss , ss + m);  
    62.         int k = 1;  
    63.         for (int i = 1 ; i < m ; i ++) {  
    64.             if (X[i] != X[i-1]) X[k++] = X[i];  
    65.         }  
    66.         memset(cnt , 0 , sizeof(cnt));  
    67.         memset(sum , 0 , sizeof(sum));  
    68.         double ret = 0;  
    69.         for (int i = 0 ; i < m - 1 ; i ++) {  
    70.             int l = Bin(ss[i].l , k , X);  
    71.             int r = Bin(ss[i].r , k , X) - 1;  
    72.             if (l <= r) update(l , r , ss[i].s , 0 , k - 1, 1);  
    73.             ret += sum[1] * (ss[i+1].h - ss[i].h);  
    74.         }  
    75.         printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++ , ret);  
    76.     }  
    77.     return 0;  
    78. }  

    hdu1828 Picture
    题意:矩形周长并
    思路:与面积不同的地方是还要记录竖的边有几个(numseg记录),并且当边界重合的时候需要合并(用lbd和rbd表示边界来辅助)
    线段树操作:update:区间增减 query:直接取根节点的值

    [cpp]  view plain  copy
     print ?
    1. #include <cstdio>  
    2. #include <cstring>  
    3. #include <cctype>  
    4. #include <algorithm>  
    5. using namespace std;  
    6. #define lson l , m , rt << 1  
    7. #define rson m + 1 , r , rt << 1 | 1  
    8.    
    9. const int maxn = 22222;  
    10. struct Seg{  
    11.     int l , r , h , s;  
    12.     Seg() {}  
    13.     Seg(int a,int b,int c,int d):l(a) , r(b) , h(c) , s(d) {}  
    14.     bool operator < (const Seg &cmp) const {  
    15.         if (h == cmp.h) return s > cmp.s;  
    16.         return h < cmp.h;  
    17.     }  
    18. }ss[maxn];  
    19. bool lbd[maxn<<2] , rbd[maxn<<2];  
    20. int numseg[maxn<<2];  
    21. int cnt[maxn<<2];  
    22. int len[maxn<<2];  
    23. void PushUP(int rt,int l,int r) {  
    24.     if (cnt[rt]) {  
    25.         lbd[rt] = rbd[rt] = 1;  
    26.         len[rt] = r - l + 1;  
    27.         numseg[rt] = 2;  
    28.     } else if (l == r) {  
    29.         len[rt] = numseg[rt] = lbd[rt] = rbd[rt] = 0;  
    30.     } else {  
    31.         lbd[rt] = lbd[rt<<1];  
    32.         rbd[rt] = rbd[rt<<1|1];  
    33.         len[rt] = len[rt<<1] + len[rt<<1|1];  
    34.         numseg[rt] = numseg[rt<<1] + numseg[rt<<1|1];  
    35.         if (lbd[rt<<1|1] && rbd[rt<<1]) numseg[rt] -= 2;//两条线重合  
    36.     }  
    37. }  
    38. void update(int L,int R,int c,int l,int r,int rt) {  
    39.     if (L <= l && r <= R) {  
    40.         cnt[rt] += c;  
    41.         PushUP(rt , l , r);  
    42.         return ;  
    43.     }  
    44.     int m = (l + r) >> 1;  
    45.     if (L <= m) update(L , R , c , lson);  
    46.     if (m < R) update(L , R , c , rson);  
    47.     PushUP(rt , l , r);  
    48. }  
    49. int main() {  
    50.     int n;  
    51.     while (~scanf("%d",&n)) {  
    52.         int m = 0;  
    53.         int lbd = 10000, rbd = -10000;  
    54.         for (int i = 0 ; i < n ; i ++) {  
    55.             int a , b , c , d;  
    56.             scanf("%d%d%d%d",&a,&b,&c,&d);  
    57.             lbd = min(lbd , a);  
    58.             rbd = max(rbd , c);  
    59.             ss[m++] = Seg(a , c , b , 1);  
    60.             ss[m++] = Seg(a , c , d , -1);  
    61.         }  
    62.         sort(ss , ss + m);  
    63.         int ret = 0 , last = 0;  
    64.         for (int i = 0 ; i < m ; i ++) {  
    65.             if (ss[i].l < ss[i].r) update(ss[i].l , ss[i].r - 1 , ss[i].s , lbd , rbd - 1 , 1);  
    66.             ret += numseg[1] * (ss[i+1].h - ss[i].h);  
    67.             ret += abs(len[1] - last);  
    68.             last = len[1];  
    69.         }  
    70.         printf("%d\n",ret);  
    71.     }  
    72.     return 0;  
    73. }  

    练习
    hdu3265 Posters
    hdu3642 Get The Treasury
    poj2482 Stars in Your Window
    poj2464 Brownie Points II
    hdu3255 Farming 
    ural1707 Hypnotoad’s Secret
    uva11983 Weird Advertisement

    多颗线段树问题

    此类题目主用特点是区间不连续,有一定规律间隔,用多棵树表示不同的偏移区间
    题意:
    维护一个有序数列{An},有三种操作:
    1、添加一个元素。
    2、删除一个元素。
    3、求数列中下标%5 = 3的值的和。

    由于有删除和添加操作,所以离线离散操作,节点中cnt存储区间中有几个数,sum存储偏移和
    [cpp]  view plain  copy
     print ?
    1. #include<iostream>  
    2. #include<cstdio>  
    3. #include<cstring>  
    4. #include<algorithm>  
    5. using namespace std;  
    6. const int maxn=100002;  
    7.   
    8. #define lson l , m , rt << 1    
    9. #define rson m + 1 , r , rt << 1 | 1   
    10.   
    11. __int64 sum[maxn<<2][6];  
    12. int cnt[maxn << 2];  
    13.   
    14. char op[maxn][20];  
    15. int a[maxn];  
    16.   
    17. int X[maxn];  
    18.   
    19. void PushUp(int rt)  
    20. {  
    21.     cnt[rt] = cnt[rt<<1] + cnt[rt<<1|1];  
    22.       
    23.     int offset = cnt[rt<<1];  
    24.     for(int i = 0; i < 5; ++i)  
    25.     {  
    26.         sum[rt][i] = sum[rt<<1][i];  
    27.     }  
    28.     for(int i = 0; i < 5; ++i)  
    29.     {  
    30.         sum[rt][(i + offset) % 5] += sum[rt<<1|1][i];  
    31.     }  
    32. }  
    33.   
    34. void Build(int l, int r, int rt)    
    35. {   /*此题Build完全可以用一个memset代替*/  
    36.     cnt[rt] = 0;  
    37.     for(int i = 0; i < 5; ++i)   sum[rt][i] = 0;  
    38.     if( l == r ) return;  
    39.     int m = ( l + r )>>1;      
    40.     Build(lson);    
    41.     Build(rson);     
    42. }   
    43.   
    44. void Updata(int p, int op, int l, int r, int rt)    
    45. {     
    46.     if( l == r )    
    47.     {    
    48.         cnt[rt] = op;   
    49.         sum[rt][1] = op * X[l-1];   
    50.         return ;    
    51.     }    
    52.     int m = ( l + r ) >> 1;    
    53.     if(p <= m)    
    54.         Updata(p, op, lson);    
    55.     else    
    56.         Updata(p, op, rson);    
    57.     
    58.     PushUp(rt);    
    59. }   
    60.   
    61. int main()  
    62. {  
    63.     int n;  
    64.     while(scanf("%d", &n) != EOF)  
    65.     {  
    66.         int nn = 0;  
    67.         for(int i = 0; i < n; ++i)  
    68.         {  
    69.             scanf("%s", &op[i]);  
    70.               
    71.             if(op[i][0] != 's')  
    72.             {  
    73.                 scanf("%d", &a[i]);  
    74.                 if(op[i][0] == 'a')  
    75.                 {  
    76.                     X[nn++] = a[i];  
    77.                 }  
    78.             }  
    79.         }  
    80.           
    81.         sort(X,X+nn);/*unique前必须sort*/  
    82.         nn = unique(X, X + nn) - X; /*去重并得到总数*/  
    83.           
    84.         Build(1, nn, 1);  
    85.           
    86.         for(int i = 0; i < n; ++i)  
    87.         {  
    88.             int pos = upper_bound(X, X+nn, a[i]) - X; /* hash */   
    89.             if(op[i][0] == 'a')  
    90.             {  
    91.                 Updata(pos, 1, 1, nn, 1);  
    92.             }  
    93.             else if(op[i][0] == 'd')  
    94.             {  
    95.                 Updata(pos, 0, 1, nn, 1);  
    96.             }  
    97.             else printf("%I64d\n",sum[1][3]);  
    98.         }  
    99.     }  
    100.     return 0;  
    101. }  

    题目:给出n个数,每次将一段区间内满足(i-l)%k==0  (r>=i>=l) 的数ai增加c, 最后单点查询。
    这种题目更新的区间是零散的,如果可以通过某种方式让离散的都变得连续,那么问题就可以用线段树完美解决。解决方式一般也是固定的,那就是利用题意维护多颗线段树。此题虚维护55颗,更新最终确定在一颗上,查询则将查询点被包含的树全部叠加。
    [cpp]  view plain  copy
     print ?
    1. #include<iostream>  
    2. #include<cstdio>  
    3. #include<cstring>  
    4. #include<cmath>  
    5. #include<algorithm>  
    6. #include<set>  
    7. #include<vector>  
    8. #include<string>  
    9. #include<map>  
    10. #define eps 1e-7  
    11. #define LL long long  
    12. #define N 500005  
    13. #define zero(a) fabs(a)<eps  
    14. #define lson step<<1  
    15. #define rson step<<1|1  
    16. #define MOD 1234567891  
    17. #define pb(a) push_back(a)  
    18. using namespace std;  
    19. struct Node{  
    20.     int left,right,add[55],sum;  
    21.     int mid(){return (left+right)/2;}  
    22. }L[4*N];  
    23. int a[N],n,b[11][11];  
    24. void Bulid(int step ,int l,int r){  
    25.     L[step].left=l;  
    26.     L[step].right=r;  
    27.     L[step].sum=0;  
    28.     memset(L[step].add,0,sizeof(L[step].add));  
    29.     if(l==r) return ;  
    30.     Bulid(lson,l,L[step].mid());  
    31.     Bulid(rson,L[step].mid()+1,r);  
    32. }  
    33. void push_down(int step){  
    34.     if(L[step].sum){  
    35.         L[lson].sum+=L[step].sum;  
    36.         L[rson].sum+=L[step].sum;  
    37.         L[step].sum=0;  
    38.         for(int i=0;i<55;i++){  
    39.                 L[lson].add[i]+=L[step].add[i];  
    40.                 L[rson].add[i]+=L[step].add[i];  
    41.                 L[step].add[i]=0;  
    42.         }  
    43.     }  
    44. }  
    45. void update(int step,int l,int r,int num,int i,int j){  
    46.     if(L[step].left==l&&L[step].right==r){  
    47.         L[step].sum+=num;  
    48.         L[step].add[b[i][j]]+=num;  
    49.         return;  
    50.     }  
    51.     push_down(step);  
    52.     if(r<=L[step].mid()) update(lson,l,r,num,i,j);  
    53.     else if(l>L[step].mid()) update(rson,l,r,num,i,j);  
    54.     else {  
    55.         update(lson,l,L[step].mid(),num,i,j);  
    56.         update(rson,L[step].mid()+1,r,num,i,j);  
    57.     }  
    58. }  
    59. int query(int step,int pos){  
    60.     if(L[step].left==L[step].right){  
    61.         int tmp=0;  
    62.         for(int i=1;i<=10;i++)  tmp+=L[step].add[b[i][pos%i]];  
    63.         return a[L[step].left]+tmp;  
    64.     }  
    65.     push_down(step);  
    66.     if(pos<=L[step].mid()) return query(lson,pos);  
    67.     else return query(rson,pos);  
    68. }  
    69. int main(){  
    70.     int cnt=0;  
    71.     for(int i=1;i<=10;i++) for(int j=0;j<i;j++) b[i][j]=cnt++;  
    72.     while(scanf("%d",&n)!=EOF){  
    73.         for(int i=1;i<=n;i++) scanf("%d",&a[i]);  
    74.         Bulid(1,1,n);  
    75.         int q,d;  
    76.         scanf("%d",&q);  
    77.         while(q--){  
    78.             int k,l,r,m;  
    79.             scanf("%d",&k);  
    80.             if(k==2){  
    81.                 scanf("%d",&m);  
    82.                 printf("%d\n",query(1,m));  
    83.             }  
    84.             else{