这是我写的第一道线段树,思路还算清晰,不过之前走了不少弯路。
主要错在:误以为线段树是一棵满二叉树,建树时吃了苦头。//线段树除了最后一层可能不满足满二叉树性质外,上面的所有层构成完全二叉树,因此仍然可以用满二叉树的性质:如果树根节点从1开始编号,则对任意编号的节点t,左子树编号为t*2,右子树编号为t*2+1,父节点编号为t/2。这样,建树的时候节点内就不用记录儿子或父节点的信息了。
下面结合poj3264说一下我对线段树的理解。
题意描述:随即给定N个奶牛(<=50000)的身高,奶牛按输入顺序编号,接下来
有Q次(<=2E5)查询,每次查询时给定两个编号a,b,要求给出编号在[a, b]之间
奶牛的身高最大差值。
要用线段树的原因很明显,线性查找一定超时。
下面是我的解题思路:
建树:
建树过程很简单,先建左右子树,再建双亲。注意节点中信息的更新。
查询:
查询过程可分为四种情况
假设节点表示的区间为[a, b],要查询的区间为[aa, bb],mid = (a+b)/2.
情况1.[aa, bb]区间正好是[a,b]区间。
情况2.[aa, bb]区间在[a, mid]区间内。
情况3.[aa, bb]区间在[mid+1, b]区间内。
情况3.[aa, bb]区间一部分在[a, mid]区间内,一部分在[mid+1, b]区间内。这种情况下需要有合并过程。也就通过比较从两部分中选出min和max。
一些细节:据说动态分配内存可能超时,所以这里用了一个数组A[]来作为开辟空间的区域。
以下是本题的代码:
#include<stdio.h>
#include<stdlib.h>
#define LEN 50010
#define LEN0 2700000 //把数组开到最大,有内存不用浪费。
typedef struct
{
int min, max;
int l, r;
int a, b;
}Node;
int count; //指向A[]中当前可用空间
Node A[LEN0];
int h[LEN];//奶牛身高
int small(int a, int b)
{
if(a < b)
return a;
return b;
}
int big(int a, int b)
{
if(a > b)
return a;
return b;
}
void MakeTree(int i)
{
int a = A[i].a;
int b = A[i].b;
int mid = (a + b) / 2;
if(a == b)//这个节点是叶子
{
A[i].min = A[i].max = h[a];
return;
}
int l = ++count;//开辟空间
int r = ++count;
A[l].a = a;
A[l].b = mid;
A[r].a = mid + 1;
A[r].b = b;
MakeTree(l);//建立左子树
MakeTree(r);//建立右子树
A[i].min = small(A[l].min, A[r].min);//更新双亲节点
A[i].max = big(A[l].max, A[r].max);
A[i].l = l;
A[i].r = r;
}
Node Query(int t, int aa, int bb)
{
int a = A[t].a;
int b = A[t].b;
if(a == aa && b == bb)//情况1
{
return A[t];
}
int mid = (a + b) / 2;
if(bb <= mid)//情况2
return Query(A[t].l, aa, bb);
if(aa >= mid + 1)//情况3
return Query(A[t].r, aa, bb);
int n1 = ++count;
int n2 = ++count;
A[n1] = Query(A[t].l, aa, mid);//情况4
A[n2] = Query(A[t].r, mid + 1, bb);
A[n1].min = small(A[n1].min, A[n2].min);//合并过程
A[n1].max = big(A[n1].max, A[n2].max);
--count;
--count;
return A[n1];
}
int main()
{
int i, j;
int N, Q;
int a, b;
scanf("%d%d", &N, &Q);
for(i = 1; i <= N; i++)
scanf("%d", &h[i]);
count = 0;
int t = ++count;
A[t].a = 1;
A[t].b = N;
MakeTree(t);
for(i = 0; i < Q; i++)
{
scanf("%d%d", &a, &b);
A[0] = Query(1, a, b);
printf("%d\n", A[0].max - A[0].min);
}
//system("pause");
}
下面是利用了满二叉树性质的代码:(同样的代码用java就超时,C++ 1563MS AC,java和C++的效率差距真的有这么大吗)
利用满二叉树性质的代码
#include<stdio.h>
#include<stdlib.h>
#include<string.h>
#include<limits.h>
#define LEN 400020
#define max(a, b) (a) > (b) ? (a) : (b)
#define min(a, b) (a) < (b) ? (a) : (b)
typedef struct Node
{
int bg, ed;
int tl, st;
}Node;
Node nds[400020];
int tals[200020];
int maxv;
int minv;
void query(int t, int bg, int ed){
if(nds[t].bg == bg && nds[t].ed == ed){
if(maxv < nds[t].tl)
maxv = nds[t].tl;
if(minv > nds[t].st)
minv = nds[t].st;
return;
}
int mid = (nds[t].bg + nds[t].ed) >> 1;
if(ed <= mid){
query(t << 1, bg, ed);
}
else if(bg > mid){
query((t << 1) + 1, bg, ed);
}
else{
query(t << 1, bg, mid);
query((t << 1) + 1, mid + 1, ed);
}
}
void makeTree(int t)
{
int bg = nds[t].bg;
int ed = nds[t].ed;
if(bg == ed){
nds[t].tl = tals[bg];
nds[t].st = tals[bg];
return;
}
int lf = t << 1;
int rt = lf + 1;
int mid = (bg + ed) >> 1;
nds[lf].bg = bg;
nds[lf].ed = mid;
makeTree(lf);
nds[rt].bg = mid + 1;
nds[rt].ed = ed;
makeTree(rt);
nds[t].tl = max(nds[lf].tl, nds[rt].tl);
nds[t].st = min(nds[lf].st, nds[rt].st);
}
int main()
{
int i, j;
int N, Q;
int a, b;
scanf("%d%d", &N, &Q);
for(int i = 1; i <= N; i++)
{
scanf("%d", &tals[i]);
}
nds[1].bg = 1;
nds[1].ed = N;
makeTree(1);
for(int i = 0; i < Q; i++)
{
scanf("%d%d", &a, &b);
maxv = INT_MIN;
minv = INT_MAX;
query(1, a, b);
printf("%d\n", maxv - minv);
}
return 0;
}
Java的超时代码
import java.util.*;
import java.util.Scanner;
class Main {
static Node nds[] = new Node[400020];
static int[] tals = new int[200020];
static int max;
static int min;
static{
for(int i = 0; i < 400020; i++)
nds[i] = new Node(0, 0);
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int N = sc.nextInt();
int Q = sc.nextInt();
for(int i = 1; i <= N; i++)
{
tals[i] = sc.nextInt();
}
nds[1].bg = 1;
nds[1].ed = N;
makeTree(1);
for(int i = 0; i < Q; i++){
int a = sc.nextInt();
int b = sc.nextInt();
max = Integer.MIN_VALUE;
min = Integer.MAX_VALUE;
query(1, a, b);
System.out.println((max - min));
}
}
static void query(int t, int bg, int ed){
if(nds[t].bg == bg && nds[t].ed == ed){
if(max < nds[t].tl)
max = nds[t].tl;
if(min > nds[t].st)
min = nds[t].st;
return;
}
int mid = (nds[t].bg + nds[t].ed) / 2;
if(ed <= mid){
query(t * 2, bg, ed);
}
else if(bg > mid){
query(t * 2 + 1, bg, ed);
}
else{
query(t * 2, bg, mid);
query(t * 2 + 1, mid + 1, ed);
}
}
static void makeTree(int t){
int bg = nds[t].bg;
int ed = nds[t].ed;
if(bg == ed){
nds[t].tl = tals[bg];
nds[t].st = tals[bg];
return;
}
int lf = t * 2;
int rt = lf + 1;
int mid = (bg + ed) / 2;
nds[lf].bg = bg;
nds[lf].ed = mid;
makeTree(lf);
nds[rt].bg = mid + 1;
nds[rt].ed = ed;
makeTree(rt);
nds[t].tl = Math.max(nds[lf].tl, nds[rt].tl);
nds[t].st = Math.min(nds[lf].st, nds[rt].st);
}
}
class Node{
int bg, ed;
int tl, st;
public Node(int tl, int st){
this.tl = tl;
this.st = st;
}
}
posted on 2012-07-29 10:44
小鼠标 阅读(1848)
评论(2) 编辑 收藏 引用 所属分类:
数据结构