随笔 - 87  文章 - 279  trackbacks - 0
<2024年3月>
252627282912
3456789
10111213141516
17181920212223
24252627282930
31123456

潜心看书研究!

常用链接

留言簿(19)

随笔分类(81)

文章分类(89)

相册

ACM OJ

My friends

搜索

  •  

积分与排名

  • 积分 - 211615
  • 排名 - 116

最新评论

阅读排行榜

评论排行榜

const int MAXN = 50000;
 
class SegmentTree {
public:
      int LSON[MAXN]; //LSON[i]为节点i的左儿子的序号
      int RSON[MAXN]; //RSON[i]为节点i的右儿子的序号
      int B[MAXN]; //B[i]为区间i左端点
      int E[MAXN]; //E[i]为区间i右端点
      int cnt[MAXN]; //cnt[i]为区间i的计数器
      int M[MAXN]; //M[i]为区间i的测度
      int lbd[MAXN]; //lbd[i]为区间i的左端点是否被覆盖
      int rbd[MAXN]; //rbd[i]为区间i的右端点是否被覆盖
      int lines[MAXN]; //lines[i]为区间i的连续线段数
      int root; //树根 初始化时候设为1
      int n; //树的节点数
      SegmentTree(int, int);
      void build(int, int);
      void insert(int, int, int);
      void del(int, int, int);
      void updateM(int); //更新测度
      void updateLines(int); //更新连续线段数
};
SegmentTree::SegmentTree(int a, int b) {
      root = 1;
      n = 0;
      memset(LSON, 0, sizeof(LSON));
      memset(RSON, 0, sizeof(RSON));
      memset(cnt, 0, sizeof(cnt));
      memset(M, 0, sizeof(M));
      memset(lines, 0, sizeof(lines));
      memset(lbd, 0, sizeof(lbd));
      memset(rbd, 0, sizeof(rbd));
      build(a, b);
}
void SegmentTree::build(int a, int b) {
      n += 1;
      int v = n;
      B[v] = a; E[v] = b; 
      if (b - a > 1) {
            LSON[v] = n + 1;
            build(a, (a+b)/2);
            RSON[v] = n + 1;
            build((a+b)/2, b);
      }
}
void SegmentTree::insert(int a, int b, int v) {
      if (!v) return ;
      if (a <= B[v] && E[v] <= b) {
            cnt[v]++;
            lbd[v] = rbd[v] = 1;
      } else if (E[v]-B[v] > 1) {
            if (a <(b[v]+e[v])/2) insert(a, b, LSON[v]);
            if (b > (B[v]+E[v])/2) insert(a, b, RSON[v]);
      }
      updateM(v);
      updateLines(v);
}
void SegmentTree::del(int a, int b, int v) {
      if (!v) return ;
      if (a <= B[v] && E[v] <= b) {
            cnt[v]--;
            if (a == B[v]) lbd[v] = 0;
            if (b == E[v]) rbd[v] = 0;
      } else if (E[v]-B[v] > 1) {
            if (a <(b[v]+e[v])/2) del(a, b, LSON[v]);
            if (b > (B[v]+E[v])/2) del(a, b, RSON[v]);
      }
      updateM(v);
      updateLines(v);
}
void SegmentTree::updateM(int v) {
      if (cnt[v] > 0) M[v] = E[v] - B[v];
      else {
            if (E[v]-B[v] == 1) M[v] = 0;
            else M[v] = M[LSON[v]] + M[RSON[v]];
      }
}
void SegmentTree::updateLines(int v) {
      if (cnt[v] > 0) lbd[v] = rbd[v] = lines[v] = 1;
      else {
            if (E[v]-B[v] == 1) lbd[v] = rbd[v] = lines[v] = 0;
            else {
                  lbd[v] = lbd[LSON[v]]; rbd[v] = rbd[RSON[v]];
                  lines[v] = lines[LSON[v]] + lines[RSON[v]] - rbd[LSON[v]] * lbd[RSON[v]];
            }
      }
}
posted on 2007-04-07 12:16 阅读(907) 评论(1)  编辑 收藏 引用 所属分类: 数据结构与算法

FeedBack:
# re: 线段树类 2008-11-14 14:19 crg511
thank you  回复  更多评论
  

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