早就听人提起过线段树，今天有题搞不出来，讨论上说要用一下线段树，看了下，本质上是空间划分索引，只不过是一维上面的，如果在二维则是四叉树，三维则是八叉树，如果可以动态调整那么跟R-Tree就很相似了，他们都可以对范围查询做出响应。参照书上写了一个，虽然不多，但是渣渣也写的很是费力
#include <iostream>
#include <cstdlib>
#include <vector> using namespace std; class SegmentTree {
private:
int *mem;
int capacity;
int storage_size;
private:
void init_level_update() {
int k = capacity - ;
while (--k >= ) {
int L = (k<<) + ;
int R = L + ;
mem[k]= min(mem[L], mem[R]);
}
} int query(int a, int b, int idx, int L, int R) {
if (b <= L || a >= R) return INT_MAX;
if (a <= L && R <= b) return mem[idx]; int ml = query(a, b, (idx<<) + , L, (L+R)/);
int mr = query(a, b, (idx<<) + , (L+R)/, R);
return min(ml, mr);
} void init_mem(int _capacity) {
if (_capacity <= ) {
capacity = ;
return;
}
int n = ;
while (n < _capacity) n<<=;
capacity = n;
storage_size = capacity * - ;
mem = new int[storage_size]; int k = ;
while (k < storage_size) mem[k++] = INT_MAX;
}
public:
SegmentTree(int _capacity) {
init_mem(_capacity);
}
SegmentTree(vector<int>::iterator begin, vector<int>::iterator end) {
capacity = end - begin;
init_mem(capacity); int k = capacity - ;
vector<int>::iterator iter = begin;
while (iter != end) mem[k++] = *iter++; init_level_update();
}
~SegmentTree() {
delete[] mem;
} // update value in original data index
void update(int idx, int val) {
if (idx >= capacity || idx < ) return;
int k = idx + capacity - ; // internal storage index
mem[k] = val;
while (k > ) {
k = (k - ) >> ;
int L = (k << ) + ;
int R = L + ;
mem[k] = min (mem[L], mem[R]);
}
} // retrive the min value in index range [a, b)
int query(int a, int b) {
return query(a, b, , , capacity);
} void print_mem(const char* msg) {
cout<<msg<<endl;
for (int i=; i<(capacity*-); i++) {
cout<<mem[i]<<" ";
}
cout<<endl;
}
}; void test(const char* msg, SegmentTree& seg_tree, int* data, int size) {
cout<<msg<<endl;
for (int i=; i<=size; i++) {
for (int j=i+; j<=size; j++) {
int tmin = seg_tree.query(i, j);
cout<<"min of ("<<i<<","<<j<<") = "<<tmin<<endl;
int amin = INT_MAX;
for (int k=i; k<j; k++) if (data[k] < amin) amin = data[k];
if (amin != tmin)
cout<<"fail"<<endl;
else
cout<<"ok"<<endl;
}
}
}
int main() {
int h[] = {, , , , , , };
int size= sizeof(h) / sizeof(int);
vector<int> hs(h, h + size); SegmentTree seg_tree(hs.begin(), hs.end());
test("Test construction with data :", seg_tree, h, size); SegmentTree init_empty_tree(size);
for (int i=; i<size; i++) init_empty_tree.update(i, h[i]);
test("Test construction without data", init_empty_tree, h, size); system("pause");
return ;
}
下面是一个带有返回最小值索引值的改进版本
class SegmentTree {
private:
int *mem;
int *idx;
int capacity;
int storage_size;
private:
void init_level_update() {
int k = capacity - ;
while (--k >= ) {
int L = (k<<) + ;
int R = L + ;
if (mem[L] < mem[R]) {
mem[k] = mem[L];
idx[k] = idx[L];
} else {
mem[k] = mem[R];
idx[k] = idx[R];
}
}
}
pair<int, int> query(int a, int b, int idx, int L, int R) {
if (b <= L || a >= R) return make_pair(INT_MAX, -);
if (a <= L && R <= b) return make_pair(mem[idx], this->idx[idx]);
pair<int, int> ml = query(a, b, (idx<<) + , L, (L+R)/);
pair<int, int> mr = query(a, b, (idx<<) + , (L+R)/, R);
return ml.first < mr.first ? ml : mr;
}
void init_mem(int _capacity) {
if (_capacity <= ) {
capacity = ;
return;
}
int n = ;
while (n < _capacity) n<<=;
capacity = n;
storage_size = capacity * - ;
mem = new int[storage_size];
idx = new int[storage_size];
int k = ;
while (k < storage_size) mem[k++] = INT_MAX;
k = capacity - ;
int i = ;
while (k < storage_size) idx[k++] = i++;
}
public:
SegmentTree(int _capacity) {
init_mem(_capacity);
}
SegmentTree(vector<int>::iterator begin, vector<int>::iterator end) {
capacity = end - begin;
init_mem(capacity);
int k = capacity - ;
vector<int>::iterator iter = begin;
while (iter != end) mem[k++] = *iter++;
init_level_update();
}
~SegmentTree() {
delete[] mem;
delete[] idx;
}
// update value in original data index
void update(int index, int val) {
if (index >= capacity || idx < ) return;
int k = index + capacity - ; // internal storage index
mem[k] = val;
while (k > ) {
k = (k - ) >> ;
int L = (k << ) + ;
int R = L + ;
if (mem[L] < mem[R]) {
mem[k] = mem[L];
idx[k] = idx[L];
} else {
mem[k] = mem[R];
idx[k] = idx[R];
}
}
}
// retrive the min value in index range [a, b)
pair<int, int> query(int a, int b) {
return query(a, b, , , capacity);
}
void print_mem(const char* msg) {
cout<<msg<<endl;
for (int i=; i<(capacity*-); i++) {
cout<<mem[i]<<" ";
}
for (int i=; i<capacity * - ; i++) {
cout<<idx[i]<<",";
}
cout<<endl;
}
};
参考：
挑战程序设计竞赛第二版