Your browser is out-of-date!

Update your browser to view this website correctly. Update my browser now

Vinllen Chen


右耳与向日葵,疯子与天才

线段树小结

  线段树是一种比较强大的数据结构,主要用于在动态更新区间的情况下,保持查找和更新在O(log(n))级别的时间复杂度。虽然它不是一颗完全二叉树,但构造时按照完全二叉树进行构树,没有的话叶结点留空,数组按完全二叉树构造:对于父节点编号为x,其左右儿子结点分别为:2x和2x+1。如下图所示:
seg
  Management range表示该结点的『负责输入结点』的范围,1-3表示负责输入结点1,2和3,即:in[1]in[2]in[3]。value值表示初始化值,刚开始构造时值为0,构造之后的值为子结点的『某种运算』结果:比如,对于『求区间最小值』,则value(4) = min(value(8), value(9))value(1) = min(value(2), value(3))`,这个在图中未标出来。图中蓝色结点为输入的结点,虚线方向为数组的输入方向(所有叶子结点)。
  模板如下,为区间求和,单点+1更新:

#define le(x) x << 1
#define ri(x) x << 1 | 1
#define lson l, m, le(rt)
#define rson m + 1, r, ri(rt)

const int SIZE = 5000;

int num[SIZE << 2];  
int x[SIZE];

void push_up(int rt)  
{
    num[rt] = num[le(rt)] + num[ri(rt)];
}

void build(int l, int r, int rt) {  
    int m = (l + r) >> 1;  
    if(l == r) {  
        scanf("%d", &num[rt]);
        return ;  
    }  
    build(l, m, le(rt));  
    build(m + 1, r, ri(rt));  
    push_up(rt);  
}

void update(int p, int l, int r, int rt)  
{
    int m;
    if(l == r) {
        num[rt] ++;
        return ;
    }
    m = (l + r) >> 1;
    if(p <= m)
        update(p, lson);
    else
        update(p, rson);
    push_up(rt);
}

//[L,R]: query interval
int query(int L, int R, int l, int r, int rt)  
{
    int m, ret = 0;
    if (L <= l && r <= R) {
        return num[rt];
    }
    m = (l + r) >> 1;
    if (L <= m)
        ret += query(L, R, lson);
    if (R > m)
        ret += query(L, R, rson);
    return ret;
}

  好吧,上题目吧。

1.hdu1166 敌兵布阵

  题意:给定n个数,有两种操作:1.单点更新 2.区间求和查询
  解题:裸题,上模板。

2.hdu1754 I Hate It

  题意:给定n个数,有两种操作:1.单点更新 2.区间最值查询
  解题:裸题,上模板。

------未完待续,太忙了,没时间刷题了


About the author

vinllen chen

Beijing, China

格物致知


Discussions

comments powered by Disqus