返回目录

---

线段树，是我们树状数组的升级版

这是一棵美丽的树

我们不难看出，每个节点的关系是这样的

第 $i$ 个节点的左节点为 $i×2$ ,右节点为 $i×2+1$

那我们就能像树状数组一样造一个树了

造树方法可以使用递归，从第一个节点开始，向下遍历，直到到达最低端时，再返回最低端的值，代码如下

#把a数组造成tree
void maketree(int k,int l,int r){
    if(l==r){#已到达底线
        f[k]=a[l];
        return;
    }
    int m=(l+r)>>1;#找到中心点对半分
    maketree(k+k,l,m);#遍历左端点
    maketreee(k+k+1,m+1,r)#遍历右端点
    f[k]=f[k+k]+f[k+k+1];
}

他都是树状数组的升级版了，肯定能够找根啊

不能……他只能从大根开始往下找，但是也很便利了

找根方式

if(l==r)return;(找到底了)
int m=(l+r)>>1;
find(k+k,l,m);
find(k+k+1,m+1,r);

既然说到了线段树，就必须得讲讲区间修改

那该怎么做呢?

那就是……懒人标记

一个个找肯定超时，那要是只找些许皮毛呢？

设立一个tag数组

他的作用是:tag[i]中装着线段树第 $i$ 个点中每个节点需要加的值，这样就不需要接着往下啦~~~

if(s>=l&&t<=r){#确保他在区间内
    tag[i]=p(一个区间要加的数值)
    tree[i]=p*(t-s+1)#更改这个树的值
}

以下为限时免费内容

ll ls(ll p){ return p<<1;  }           //定位左儿子：p*2
ll rs(ll p){ return p<<1|1;}           //定位右儿子：p*2 + 1



void push_up(ll p){                    //从下往上传递区间值
    tree[p] = tree[ls(p)] + tree[rs(p)];  
}//此处为区间和。如果求最小值，改为：tree[p] = min(tree[ls(p)], tree[rs(p)]);




void build(ll p,ll pl,ll pr){    //建树。p是结点编号(第p个点)，它指向区间[pl, pr](包括了pl,pr)
    tag[p] = 0;                         //lazy-tag标记
    if(pl==pr){
		tree[p]=a[pl]; 
		return;
	}  									//最底层的叶子，赋值    
    ll mid = (pl+pr) >> 1;              //分治：折半
    build(ls(p),pl,mid);                //左儿子
    build(rs(p),mid+1,pr);              //右儿子
    push_up(p);                         //从下往上传递区间值
} 



void addtag(ll p,ll pl,ll pr,ll d){     //给结点p打tag标记，并更新tree
    tag[p] += d;                        //打上tag标记
    tree[p] += d*(pr-pl+1);             //计算新的tree
}



void push_down(ll p,ll pl,ll pr){       //不能覆盖时，把tag传给子树(从上向下传递tag值) 
    if(tag[p]){                         //有tag标记，这是以前做区间修改时留下的
        ll mid = (pl+pr)>>1; 
        addtag(ls(p),pl,mid,tag[p]);    //把tag标记传给左子树
        addtag(rs(p),mid+1,pr,tag[p]);  //把tag标记传给右子树
        tag[p]=0;                       //p自己的tag被传走了，归0
    }
}



void update(ll L,ll R,ll p,ll pl,ll pr,ll d){ //区间修改：把[L, R]内每个元素加上d
    if(L<=pl && pr<=R){       //完全覆盖，直接返回这个结点，它的子树不用再深入了    
        addtag(p, pl, pr,d);  //给结点p打tag标记，下一次区间修改到p时会用到
		return;                    
    }
    push_down(p,pl,pr);                 //如果不能覆盖，把tag传给子树
    ll mid=(pl+pr)>>1;
    if(L<=mid) update(L,R,ls(p),pl,mid,d);    //递归左子树
    if(R>mid)  update(L,R,rs(p),mid+1,pr,d);  //递归右子树
    push_up(p);                               //更新
}



ll query(ll L,ll R,ll p,ll pl,ll pr){
  //查询区间[L,R]；p是当前结点（线段）的编号，[pl,pr]是结点p表示的线段区间
    if(pl>=L && R >= pr) return tree[p];       //完全覆盖，直接返回
    
    push_down(p,pl,pr);                        //不能覆盖，递归子树
    ll res=0;
    ll mid = (pl+pr)>>1;
    if(L<=mid) res+=query(L,R,ls(p),pl,mid);   //左子结点有重叠
    if(R>mid)  res+=query(L,R,rs(p),mid+1,pr); //右子结点有重叠
    return res;
}

```