岳父与小明：农夫约翰有N头牛排成一列，他从第A头牛到第B头牛里挑出最高的那头取名叫岳父，最矮的那头取名叫小明。求岳父与小明的身高差？
即
给出初始化的区间值，m次查询
每次查询区间[a，b]的最大值－最小值
题目大意: 给出初始化的区间值，m次查询
每次查询区间[a，b]的最大值－最小值
解题思路: 线段树 更新: 无更新 查询:区间查询
建立线段树的时候，每个结点存储左右子树的最大值和最小值
查询时直接访问区间最大值和最小值，不需要查找到最低
查询时间复杂度O(logN)
#include <stdio.h> #include <stdlib.h> #include <string.h> #define MAXN 70000 #define INF 0x3f3f3f3f #define MAX(a,b) a>b?a:b #define MIN(a,b) a<b?a:b #define MID(a,b) (a+b)>>1 #define L(a) a<<1 #define R(a) (a<<1)+1 typedef struct snode{ int left,right; int max,min; }Node; Node Tree[MAXN<<1]; int num[MAXN],minx,maxx; void Build(int t,int l,int r) ///以t为根结点建立左子树为l，右子树为r的线段树 { int mid; Tree[t].left=l,Tree[t].right=r; if(Tree[t].left==Tree[t].right)///区间变为点 { Tree[t].max=Tree[t].min=num[l]; return ; } mid=MID(Tree[t].left,Tree[t].right); Build(L(t),l,mid);///左右子树 Build(R(t),mid+1,r); Tree[t].max=MAX(Tree[L(t)].max,Tree[R(t)].max); ///更新结点的最大值=MAX(左子树，右子树) Tree[t].min=MIN(Tree[L(t)].min,Tree[R(t)].min); ///更新结点的最小时=MIN(左子树，右子树) } void Query(int t,int l,int r) ///查询结点为t，左子树为l，右子树为r的最大值和最小值 { int mid; if(Tree[t].left==l&&Tree[t].right==r) { if(maxx<Tree[t].max) maxx=Tree[t].max; if(minx>Tree[t].min) minx=Tree[t].min; return ; } mid=MID(Tree[t].left,Tree[t].right); if(l>mid) { Query(R(t),l,r); } else if(r<=mid) { Query(L(t),l,r); } else { Query(L(t),l,mid); Query(R(t),mid+1,r); } } int main() { int n,m,a,b,i; memset(Tree,0,sizeof(Tree)); scanf("%d%d",&n,&m); for(i=1;i<=n;i++) scanf("%d",&num[i]); Build(1,1,n); ///建立以1为根结点区间为[1,n]的线段树 while(m--) { scanf("%d%d",&a,&b); maxx=0;minx=INF; ///初始化最大值为0,最小值为INF Query(1,a,b); ///查询区间[a,b]的最大值和最小值 printf("%d ",maxx-minx); } return 0; }
线段树和平方分割
平方分割我觉得是一种分治的思想，它所追求的不是分治的最终结果，而是过程的中间结果。将这N头牛平方分割放入sqrt(N)个桶，每个桶只需记录桶里最高和最矮的两个身高值即可。然后完全包含在区间的桶里直接考虑这两个值，否则从原始数据里比较。
唯一需要注意的是这里的下标问题，下标从零开始的话，在求模的时候需要注意：左边界 mod bucket_size == 0时左边界恰好落入桶，(右边界 + 1) mod bucket_size == 0时右边界才恰好落入桶，两者不一样的。
#include <iostream> #include <vector> #include <algorithm> #include <cmath> #include "cstdio" using namespace std; #define MAX_N 50000 + 16 int H[MAX_N]; // 输入N头牛的高度 vector<pair<int, int> > bucket; // 对每个桶内高度的最小值与最大值的记录 ///////////////////////////SubMain////////////////////////////////// int main(int argc, char *argv[]) { #ifndef ONLINE_JUDGE //freopen("in.txt", "r", stdin); //freopen("out.txt", "w", stdout); #endif int N, Q; scanf("%d%d", &N, &Q); const int bucket_size = sqrt((float)N); // error C2668: 'sqrt' : ambiguous call to overloaded function bucket.resize(bucket_size + 1); for (int i = 0; i < bucket_size + 1; ++i) { bucket[i].first = 0x3f3f3f3f; bucket[i].second = 0x80808080; } for (int i = 0; i < N; ++i) { scanf("%d", &H[i]); bucket[i / bucket_size].first = min(bucket[i / bucket_size].first, H[i]); bucket[i / bucket_size].second = max(bucket[i / bucket_size].second, H[i]); } for (int i = 0; i < Q; ++i) { int A, B; scanf("%d%d", &A, &B); if (A == B) { puts("0"); continue; } int min_height = 0x3f3f3f3f; int max_height = 0x80808080; int l = A - 1, r = B; // 区间两端多出来的部分 while (l < r && l % bucket_size != 0) { int h = H[l++]; min_height = min(min_height, h); max_height = max(max_height, h); } while (l < r && r % bucket_size != 0) { int h = H[--r]; min_height = min(min_height, h); max_height = max(max_height, h); } // 对每一个桶进行计算 while (l < r) { int b = l / bucket_size; min_height = min(min_height, bucket[b].first); max_height = max(max_height, bucket[b].second); l += bucket_size; } printf("%d ", max_height - min_height); } /* #ifndef ONLINE_JUDGE fclose(stdin); fclose(stdout); system("out.txt"); #endif*/ return 0; }