|
Posted on 2009-08-28 09:11 reiks 阅读(269) 评论(0) 编辑 收藏 引用 所属分类: 算法与数据结构
#include <iostream>
using namespace std;
#define N 100
struct TNode
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
int left, right;
int n;
};
TNode T[N*2+1];
void build(int s, int t, int step)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
if(s == T[step].left && t == T[step].right)
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedSubBlockStart.gif) {
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
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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()
![](http://www.cppblog.com/Images/OutliningIndicators/ExpandedBlockStart.gif) ![](http://www.cppblog.com/Images/OutliningIndicators/ContractedBlock.gif) {
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;
}
![](http://www.cppblog.com/Images/OutliningIndicators/None.gif)
|