作为一个初学者，在这里就当是记一下笔记了

线段树是一种RMQ（区间最大值）与树状数组（区间求和）的结合，用到了分治思想

时间复杂度为nlogn，与树状数组和RMQ一样，但是有一个比较大的常数

多用于数列

多用于线段

用完全二叉数的储存方式储存

可以用结构体，也可以只用数组储存，差不多

线段树的功能

一、单点操作

单点修改，区间求和，区间求最值

二、区间操作

成段操作，区间求和，区间求最值

三、区间合并

四、扫描线

后两个有时间再上，我还没学完啦

build

#define lson l,m,rt<<1#define rson m+1,r,rt<<1|1void 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;}

这个不大难，

单点更新习题：

hdu1166 敌兵布阵

hdu1754 I Hate It

hdu1394 Minimum Inversion Number

hdu2795 Billboard

poj2828 Buy Tickets

二、区间更新

需要用到延迟标记(或者说懒惰标记),简单来说就是每次更新的时候不要更新

到底,用延迟标记使得更新延迟到下次需要更新or询问到的时候。

具体操作为：

延迟标记：每个节点新增加一个标记，记录这个节点是否进行了某种修改

(这种修改操作会影响其子节点)，对于任意区间的修改，我们先按照区间查

询的方式将其划分成线段树中的节点，然后修改这些节点的信息，并给这些

节点标记上代表这种修改操作的标记。在修改和查询的时候，如果我们到了

一个节点p，并且决定考虑其子节点，那么我们就要看节点p是否被标记，如

果有，就要按照标记修改其子节点的信息，并且给子节点都标上相同的标

记，同时消掉节点p的标记。

一道坎，会了就不难了

延迟标记PushDown

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

区间修改或更新

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

区间查询

LL query(int L,int R,int l,int r,int rt){    if(L <= l && r <= R){        return sum[rt];    }    PushDown(rt , r - l +1);    int m =(l + r)>>1;    LL ret =0;    if(L <= m) ret += query(L , R , lson);    if(m < R) ret += query(L , R , rson);    return ret;}

区间更新习题：

hdu1698 Just a Hook

poj3468 A Simple Problem with Integers

poj2528 Mayor’s posters

poj3225 Help with Intervals (较难)

Bzoj1798 Ahoi2009行星序列

区间合并

求连续最长序列

这类题目会询问区间中满足条件的连续最长区间,所以PushUp的时候需要对左右儿子的区间进行合并

void PushUp(int rt,int m){    lsum[rt]= lsum[rt<<1];    rsum[rt]= rsum[rt<<1|1];    if(lsum[rt]== m -(m >>1)) lsum[rt]+= lsum[rt<<1|1];    if(rsum[rt]==(m >>1)) rsum[rt]+= rsum[rt<<1];    msum[rt]= max(lsum[rt<<1|1]+ rsum[rt<<1] , max(msum[rt<<1] , msum[rt<<1|1]));}

查询

int query(int w,int l,int r,int rt){    if(l == r)return l;    PushDown(rt , r - l +1);    int m =(l + r)>>1;    if(msum[rt<<1]>= w)return query(w , lson);    elseif(rsum[rt<<1]+ lsum[rt<<1|1]>= w)return m - rsum[rt<<1]+1;    return query(w , rson);}

剩下的自己调吧

扫描线

据说是码农题，所以，我也没怎么做

用来求面积并或者是周长并

hdu1542 Atlantis

#include 
      
       #include 
       
        #include 
        
         #include 
         
          usingnamespace std;#define lson l , m , rt << 1#define rson m + 1 , r , rt << 1 | 1 constint maxn =2222;int cnt[maxn <<2];double sum[maxn <<2];double X[maxn];struct Seg {    double h , l , r;    int s;    Seg(){}    Seg(double a,double b,double c,int d): l(a) , r(b) , h(c) , s(d){}    bool operator <(const Seg &cmp)const{        return h < cmp.h;    }}ss[maxn];void PushUp(int rt,int l,int r){    if(cnt[rt]) sum[rt]= X[r+1]- X[l];    elseif(l == r) sum[rt]=0;    else sum[rt]= sum[rt<<1]+ sum[rt<<1|1];}void update(int L,int R,int c,int l,int r,int rt){    if(L <= l && r <= R){        cnt[rt]+= c;        PushUp(rt , l , r);        return;    }    int m =(l + r)>>1;    if(L <= m) update(L , R , c , lson);    if(m < R) update(L , R , c , rson);    PushUp(rt , l , r);}int Bin(double key,int n,double X[]){    int l =0 , r = n -1;    while(l <= r){        int m =(l + r)>>1;        if(X[m]== key)return m;        if(X[m]< key) l = m +1;        else r = m -1;    }    return-1;}int main(){    int n , cas =1;    while(~scanf("%d",&n)&& n){        int m =0;        while(n --){            double a , b , c , d;            scanf("%lf%lf%lf%lf",&a,&b,&c,&d);            X[m]= a;            ss[m++]= Seg(a , c , b , 1);            X[m]= c;            ss[m++]= Seg(a , c , d , -1);        }        sort(X , X + m);        sort(ss , ss + m);        int k =1;        for(int i =1; i < m ; i ++){            if(X[i]!= X[i-1]) X[k++]= X[i];        }        memset(cnt , 0 , sizeof(cnt));        memset(sum , 0 , sizeof(sum));        double ret =0;        for(int i =0; i < m -1; i ++){            int l = Bin(ss[i].l , k , X);            int r = Bin(ss[i].r , k , X)-1;            if(l <= r) update(l , r , ss[i].s , 0 , k -1, 1);            ret += sum[1]*(ss[i+1].h- ss[i].h);        }        printf("Test case #%d\nTotal explored area: %.2lf\n\n",cas++ , ret);    }    return0;}
         
        
       
      

就到这里吧，周长并比面积并难多了...