学习线段树的一点心得

时间：2022-10-27 11:11:31

其实现在我越来越感觉，自己以前还是犯错误了，过于注重结果，过于注重代码的写法和AC，很多东西都没有搞清楚原理。

尤其是在学习线段树的时候，还有昨天搞那个POJ 2886涉及到的筛法还有求反素数的时候，都深深体会到弄懂原理是多么的重要。以后一定要注重原理。


对于线段树的学习，目前还在学习中，但是还是想把心得写下来，避免时间久了就忘了。



一、对于单点更新的线段树

目前遇到的类型有，单点更新，区间求和，单点替换，区间最值。感觉做线段树的题目还是重在抽象出模型吧，很多题目都是这样。不把题目中的条件抽象到线段树的区间和点上来还是无法应用这些数据结构。所以说么，思想最重要。

单点更新的线段树还是很简单的，类似树状数组，很多题目也可以用树状数组来解决，但是线段树的应用范围更广，比如题目不满足减法规则的时候，就必须要用线段树。

至于操作方面，我还是按着模板来，根据题目的需求做一些改动


1、线段树功能:update:单点增减 query:区间求和
void PushUP(int rt) {
sum[rt] = sum[rt<<1] + sum[rt<<1|1];
}
void build(int l,int r,int rt) {
if (l == r) {
scanf("%d",&sum[rt]);
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUP(rt);
}
void update(int p,int add,int l,int r,int rt) {
if (l == r) {
sum[rt] += add;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(p , add , lson);
else update(p , add , rson);
PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) {
return sum[rt];
}
int m = (l + r) >> 1;
int ret = 0;
if (L <= m) ret += query(L , R , lson);
if (R > m) ret += query(L , R , rson);
return ret;
}

2、线段树功能:update:单点替换 query:区间求最大值

void PushUP(int rt) {
MAX[rt] = max(MAX[rt<<1] , MAX[rt<<1|1]);
}
void build(int l,int r,int rt) {
if (l == r) {
scanf("%d",&MAX[rt]);
return ;
}
int m = (l + r) >> 1;
build(lson);
build(rson);
PushUP(rt);
}
void update(int p,int sc,int l,int r,int rt) {
if (l == r) {
MAX[rt] = sc;
return ;
}
int m = (l + r) >> 1;
if (p <= m) update(p , sc , lson);
else update(p , sc , rson);
PushUP(rt);
}
int query(int L,int R,int l,int r,int rt) {
if (L <= l && r <= R) {
return MAX[rt];
}
int m = (l + r) >> 1;
int ret = 0;
if (L <= m) ret = max(ret , query(L , R , lson));
if (R > m) ret = max(ret , query(L , R , rson));
return ret;
}

二、更改区间，查询单点。第二类和第三类，都要换一种方法，而这些方法的基础就是LAZY思想，即，每次更新的时候，无论更新区间还是一个点，我们都只需要把区间和向上更新即可，即更新树的祖先。而向下面的孩子节点暂且不用更新，只是在原来有更新操作的区间上做一个标记，标记对整个区间所更更新的增量。当我们要查询原来更新过的节点的孩子节点的时候，从根节点开始向下走，如果遇到标记不为0的点，那么我们就把标记传递下去，直到我们所求的区间或短点。

（1）区间更新，查询单点。这里的话，如果是查询单点，我的理解是不用管区间和值，因为一旦做了标记之后，如果要查询单点，即叶子节点，那么标记值会一直传递下去，在传递的过程中我们只要把标记值累加就好，最后当我们查询到叶子节点的时候，既可以得到单点更新后的最终结果，也能够得到单点的增量，即传递下来的标记值。

void pushdown(int rt,int m)
{
if(tot[rt])
{
tot[rt<<1]+=tot[rt];
tot[rt<<1|1]+=tot[rt];
tot[rt]=0;          //传递完成归0
}

}

（2）区间更新，查询区间的时候，pushdown函数自然也要把区间和的数据传递下去。 

void pushdown(int rt,int m)
{
if(tot[rt])
{
tot[rt<<1]+=tot[rt];
tot[rt<<1|1]+=tot[rt];
sum[rt<<1]+=(m-(m>>1))*tot[rt];
sum[rt<<1|1]+=(m>>1)*tot[rt];
tot[rt]=0;          //传递完成归0
}

}

（3）区间替换的话，直接传递下去就行，不用累加，因为最终会替换成你要求的结果，之所以做传递操作是因为，如果接下来我想查询某个区间的和值的话，还是会用到上面传递下来的数据。 


void pushdown(int rt,int m)
{
if(tot[rt])
{
tot[rt<<1]=tot[rt<<1|1]=tot[rt];
sum[rt<<1]=tot[rt]*(m-(m>>1));
sum[rt<<1|1]=tot[rt]*(m>>1);
tot[rt]=0;
}

}
三、每次查询的时候，如果碰到标记不为0的点都要向下传递 

void update(int L,int R,int add,int l,int r,int rt)
{
if(L<=l&&r<=R)
{
sum[rt]=add*(r-l+1);
tot[rt]=add;
return ;
}
pushdown(rt,r-l+1);
int m=(l+r)>>1;
if(L<=m) update(L,R,add,lson);
if(R>m)update(L,R,add,rson);
pushup(rt);
}


这个笔记还是不完全毕竟做的练习有限，遇到新的情况我会及时更新上来

再次附上我的练习：


Solved Problem ID Title Ratio(Accepted / Submitted)
学习线段树的一点心得 1001 敌兵布阵 50.93%(55/108)
  1002 覆盖的面积 100.00%(5/5)
学习线段树的一点心得 1003 Minimum Inversion Number 70.21%(33/47)
  1004 Tunnel Warfare 35.29%(12/34)
  1005 Atlantis 34.62%(9/26)
学习线段树的一点心得 1006 Just a Hook 36.78%(32/87)
学习线段树的一点心得 1007 I Hate It 57.75%(41/71)
  1008 Luck and Love 15.79%(3/19)
  1009 Picture 100.00%(4/4)
学习线段树的一点心得 1010 Billboard 44.90%(22/49)
  1011 Memory Control 25.00%(2/8)
  1012 Man Down 50.00%(2/4)
  1013 Flowers Placement 0.00%(0/0)
  1014 Posters 20.00%(2/10)
  1015 LCIS 40.00%(2/5)
  1016 Sequence operation 16.67%(1/6)
  1017 Get The Treasury 50.00%(1/2)


标签：

相关文章