Try Again

基础知识学习
随笔 - 4, 文章 - 0, 评论 - 0, 引用 - 0
数据加载中……

线段树

#include <iostream>
#include 
<string>
#include 
<algorithm>
using namespace std;

const int SIZE = 10010;

struct node // the node of line tree
{
    
int i,j; // 区间范围
    node * lson;
    node 
* rson;
    
int count; // 线段覆盖条数
    int m; // 测度
    int line; // 连续段数
    int lbd,rbd; // 用来计算连续段数
    node(int l,int r)
    {
        i 
= l,j = r;
        count 
= m = line = lbd = rbd = 0;
        lson 
= rson = NULL;
    }
};
class LineTree
{
    node 
* head;
    
/* 以下函数内部使用,可不用考虑 */
    
void init(node * pnode = NULL)
    {
        head 
= pnode;
    }
    
void updateM()
    {
        
if (head->count > 0// 被覆盖满
            head->= head->- head->i;
        
else if (head->- head->== 1// 该节点为叶节点
            head->= 0;
        
else    // 其他内部节点的情况
            head->= (head->lson)->+ (head->rson)->m;
    }
    
void updateLine()
    {
        
if (head->count > 0)
            head
->lbd = head->rbd = head->line = 1;
        
else if (head->- head->== 1)
            head
->lbd = head->rbd = head->line = 0;
        
else
        {
            head
->lbd = (head->lson)->lbd;
            head
->rbd = (head->rson)->rbd;
            head
->line = (head->lson)->line + (head->rson)->line - (head->lson)->rbd * (head->rson)->lbd;
        }
    }
public:
    LineTree();
    
void clear(); // 清空线段数;
    void build(int l,int r); // 建立线段树,区间[l,r];
    void insert(int l,int r); // 插入一条线段;
    void del(int l,int r); // 删除一条线段;
    int GetM(); // 测度;
    int GetLine(); // 连续段数;
    int GetCov(); // 覆盖线段数;
    ~LineTree();
};
LineTree::LineTree()
{
    head 
= NULL;
}
void LineTree::clear() // 清空线段数
{
    
if (head == NULL)
        
return;
    LineTree temp;
    temp.init(head
->lson);
    temp.clear();
    temp.init(head
->rson);
    temp.clear();
    delete head;
    head 
= NULL;
}
void LineTree::build(int l,int r) // 建立线段树,区间[l,r]
{
    head 
= new node(l,r);
    
if (r - l > 1)
    {
        
int k = (l + r) / 2;
        LineTree temp;
        temp.build(l,k);
        head
->lson = temp.head;
        temp.init();
        temp.build(k,r);
        head
->rson = temp.head;
    }
}
void LineTree::insert(int l,int r) // 插入一条线段
{
    
if (l <= head->&& r >= head->j)
        (head
->count)++;
    
else
    {
        LineTree temp;
        
if (l < (head->i+head->j)/2)
        {
            temp.init(head
->lson);
            temp.insert(l,r);
        }
        
if (r > (head->i+head->j)/2)
        {
            temp.init(head
->rson);
            temp.insert(l,r);
        }
    }
    updateM();
    updateLine();
}
void LineTree::del(int l,int r) // 删除一条线段
{
    
if (l <= head->&& head-><= r)
        (head
->count)--;
    
else
    {
        LineTree temp;
        
if (l < (head->i+head->j)/2)
        {
            temp.init(head
->lson);
            temp.del(l,r);
        }
        
if (r > (head->i+head->j)/2)
        {
            temp.init(head
->rson);
            temp.del(l,r);
        }
    }
    updateM();
    updateLine();
}
int LineTree::GetM() // 测度
{
    
return head->m;
}
int LineTree::GetLine() // 连续段数
{
    
return head->line;
}
int LineTree::GetCov() // 覆盖线段数
{
    
return head->count;
}
LineTree::
~LineTree()
{
    
this->clear();
}

posted on 2008-08-05 09:24 NicYun 阅读(4228) 评论(0)  编辑 收藏 引用 所属分类: Algorithm


只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理