### 线段树

362

{% blockquote 百度百科 http://baike.baidu.com/view/670683.htm 线段树%}

{% endblockquote %}

# 最简单的线段树

## 结构定义

struct Tree{
int l,r;
int n;
};

lr 是线段树的两个端点
n 是线段树的这个结点存储的数值,可以根据具体需要更改

## 建树

compare 是函数指针,可以是 max 或者 min 用于确定是要最大值还是最小值

int BuildTree(int a,int b,int (*compare)(int,int),int* num,Tree *T,int pos = 1) {
T[pos].l = a;
T[pos].r = b;
if(b - a == 1)
return T[pos].n = compare(num[a],num[b]);

int mid = (a + b) / 2;
int leftchild = 2 * pos;
int rightchild = 2 * pos + 1;

T[pos].n = compare(
BuildTree(a,mid,compare,num,T,leftchild),
BuildTree(mid,b,compare,num,T,rightchild)
);
}

## 查询

int GetNum(int a,int b,int(*compare)(int,int),int* num,Tree *T,int pos = 1) {
if(a == b)
return num[a];

int &l = T[pos].l;
int &r = T[pos].r;

if(a == l && b == r)
return T[pos].n;

int mid = (l + r) / 2;
int leftchild = 2 * pos;
int rightchild = 2 * pos + 1;

if(b <= mid)
return GetNum(a,b,compare,num,T,leftchild);
if(a >= mid)
return GetNum(a,b,compare,num,T,rightchild);

return T[pos].n = compare(
GetNum(a,mid,compare,num,T,leftchild),
GetNum(mid + 1,b,compare,num,T,rightchild)
);
}

• 点击查看/关闭被识别为广告的评论