本文共 1863 字，大约阅读时间需要 6 分钟。

距离NOIP还有不到10天深感压力之重。。。

线段树 是一个维护区间信息的数据结构 可以做到NlogN之内修改查询

先写一个区间修改区间求和的吧

一开始居然wa了  看来是学过太久没有复习了

要注意的地方有

pushdown()里的lazy下传不能仅仅赋值 要加上lazy[o]

add要先pushdown再向下递归再pushup

#include
   
    #include
    
     #include
     
      using namespace std;const int lim=200011;long long sumv[lim<<2];long long lazy[lim<<2];int m,n,a,b,c;void pushup(int o){sumv[o]=sumv[o<<1]+sumv[o<<1|1];}void pushdown(int o,int l,int r){	if(lazy[o])	{		int m=(l+r)>>1;		lazy[o<<1]+=lazy[o];		lazy[o<<1|1]+=lazy[o];		sumv[o<<1]+=(m-l+1)*lazy[o];		sumv[o<<1|1]+=(r-m)*lazy[o];		lazy[o]=0;		pushup(o);	}}void build(int o,int l,int r){	if(l==r)	{		scanf("%d",&sumv[o]);		return;	}	int m=(l+r)>>1;	build(o<<1,l,m);	build(o<<1|1,m+1,r);	pushup(o);}int x,y;long long query(int o,int l,int r){	if(l>=x&&r<=y)return sumv[o];	pushdown(o,l,r);	int m=(l+r)>>1;	long long ret=0;	if(x<=m)ret+=query(o<<1,l,m);	if(y>m)ret+=query(o<<1|1,m+1,r);	return ret;}long long inc;void add(int o,int l,int r){	if(l>=x&r<=y)	{		sumv[o]=sumv[o]+(r-l+1)*inc;		lazy[o]=lazy[o]+inc;		return;	}	int m=(l+r)>>1;	pushdown(o,l,r);	if(x<=m)add(o<<1,l,m);	if(y>m)add(o<<1|1,m+1,r);	pushup(o);}int main(){	scanf("%d",&m);	build(1,1,m);	scanf("%d",&n);	for(a=1;a<=n;a++)	{		scanf("%d%d%d",&b,&x,&y);		if(b==1)		{			scanf("%d",&inc);			add(1,1,m);		}		else		{			cout<
      
       <<'\n';		}	}	return 0;}
      
     
    
   

其次还有线段树的几个题目和注意事项

1.苹果树 DFS序列表示区间 线段树维护区间信息

题目见 POJ 3321

这个题难点不是线段树 是用dfs序表示区间

2.约瑟夫环问题

有数学方法可以在On的时间内求出最后出圈人(当然我不会)

利用线段树可以在NlogN的时间内求出出圈顺序

当前出圈人是第pos人 下一次是第pos+n-1人 因为刚才pos出去了 所以要-1  为了防止它大于sumv[1] 所以要%sumv[1] 又为了防止它是第0个人 所以特判一下

注意是人不是编号  而线段树维护的就是在圈内的人的数量

所以可以递归找到是哪个根节点 然后输出它的编号

3.黑匣子   求区间K小

蒟蒻不会平衡树 双堆求连续增长的k小可以 线段树也可以！

首先可以用线段树支持一下几个操作

1.给出x，使f[x]+1

2.求

i<=x-1                       i<=x

    Σ         f[i]<k   且     Σ     f[i]>=k          时的x

   i=1                          i=1

4. NOIP2012 DAY2 T2借教室

虽然正解不是线段树 但是可以拿到90

顺便说下正解是二分  恩 又是二分！！！

5. 两种不同的建树思想

COGS 

数列

三元数对

估计今后不会再碰线段树了

Noip RP++

转载地址：https://blog.csdn.net/li412302070/article/details/13761409 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！