|
|
Posted on 2009-08-28 09:11 reiks 阅读(269) 评论(0) 编辑 收藏 引用 所属分类: 算法与数据结构
 #include <iostream>
using namespace std;
#define N 100
struct TNode
   {
 int left, right;
int n;
 };
TNode T[N*2+1];
void build(int s, int t, int step)
{
T[step].left = s;
T[step].right = t;
T[step].n = 0;
if(s == t)
return;
int mid = (s + t) / 2;
build(s, mid, step*2);
build(mid+1, t, step*2+1);
}
void insert(int s, int t, int step)
// insert [s, t] in the tree
{
if(s == T[step].left && t == T[step].right)
  {
T[step].n++;
return;
 }
int mid = (T[step].left + T[step].right) / 2;
if(t <= mid)
insert(s, t, step*2);
else if(s > mid)
insert(s, t, step*2+1);
else
{
insert(s,mid, step*2);
insert(mid+1, t, step*2+1);
}
}
void calculate(int s, int t, int step, int target, int& count)
// caculate target in the tree
{
count += T[step].n;
if(s == t)
return;
int mid = (s + t) / 2;
if(target <= mid)
calculate(s, mid, step*2, target, count);
else
calculate(mid+1, t, step*2+1, target, count);
}
int main()
{
build(0, 7, 1);
insert(2, 5, 1);
insert(4, 6, 1);
insert(0, 7, 1);
int count = 0;
calculate(0, 7, 1, 4, count);
cout << count << endl;
return 0;
}
|