线段树（区间树）

1.基本概念

线段树，Segment tree，是一颗二叉树，树的每个节点代表一个区间[a,b]。故又叫做区间树，Interval tree。

用于解决线段的并，或区间覆盖问题。

性质：线段树是平衡二叉树，最大深度为logN(N为线段树所表示区间的长度)。

2.线段树API

存储结构：

public class Node
{
    public int left;
    public int right;
    public int value;
    public Node leftChild;
    public Node rightChild;
}

l BuildTree(a,b)

建一棵从a到b的空线段树；

Node BuildTree(int a, int b)
{
    Node node = new Node();
    node.left = a;
    node.right = b;
    node.value = 0;
    if (a == b) return node;
    node.leftChild = BuildTree(a, (a + b) / 2);
    node.rightChild = BuildTree((a + b) / 2, b);
    return node;
}

l Insert(T,c,d,value)

将区间[c,d]插入线段树T中；

并维护节点信息value

void Insert(Node p, int c, int d, int key)
{
    if (c <= p.left && p.right <= d)
    {
        p.value = key;
        return;
    }

    if (c <= (p.left + p.right) / 2)
    {
        Insert(p.leftChild, c, d, key);
    }
    if (d > (p.left + p.right) / 2)
    {
        Insert(p.rightChild, c, d, key);
    }
}

l Delete(T,c,d,value)

将区间[c,d从线段树T中删除；

并维护节点信息value

void Delete(Node p, int c, int d)
{
    if (c <= p.left && p.right <= d)
    {
        p.value = 0;
        return;
    }

    if (c <= (p.left + p.right) / 2)
    {
        Delete(p.leftChild, c, d);
    }
    if (d > (p.left + p.right) / 2)
    {
        Delete(p.rightChild, c, d);
    }
}

l Search(T,c,d)

从T中查找[c,d]的节点信息

int Search(Node p, int a, int b)
{
    int ans = 0;
    if (a <= p.left && p.right <= b)
    {
        ans = p.value;
        return ans;
    }

    if (a <= (p.left + p.right) / 2)
    {
        ans = Search(p.leftChild, a, b);
    }
    if (b > (p.left + p.right) / 2)
    {
        ans = Search(p.rightChild, a, b);
    }

    return ans;
}

l TreeLength(T)

计算T的测度，即线段树的覆盖程度

int QLen(Node p)
{
    if (p.value > 0)
    {
        return p.right - p.left;
    }
    else if (p.right - p.left == 0) return 0;
    else
        return QLen(p.leftChild) + QLen(p.rightChild);
}

3.离散化思想

离散化：离散化，把无限空间中有限的个体映射到有限的空间中去，以此提高算法的时空效率。

参考百度百科

线段离散化方法：先对起点进行排序，然后计算区间覆盖