本文共 3650 字，大约阅读时间需要 12 分钟。

士兵杀敌（三）南里123题

时间限制：2000 ms  |  内存限制：65535 KB

难度：5

描述

南将军统率着N个士兵，士兵分别编号为1~N,南将军经常爱拿某一段编号内杀敌数最高的人与杀敌数最低的人进行比较，计算出两个人的杀敌数差值，用这种方法一方面能鼓舞杀敌数高的人，另一方面也算是批评杀敌数低的人，起到了很好的效果。

所以，南将军经常问军师小工第i号士兵到第j号士兵中，杀敌数最高的人与杀敌数最低的人之间军功差值是多少。

现在，请你写一个程序，帮小工回答南将军每次的询问吧。

注意，南将军可能询问很多次。

输入

只有一组测试数据

输出

对于每次询问，输出第m号士兵到第n号士兵之间所有士兵杀敌数的最大值与最小值的差。

样例输入

5 2

1 2 6 9 3

1 2

2 4

样例输出

1

7

#include
   
    #define max(a, b) a > b ? a : b#define min(a, b) a > b ? b : aint Ma[2100005], Mi[2100005], Ma1, Mi1;void build(int L, int R, int pos) {  if (L == R) {    scanf("%d", &Ma[pos]);    Mi[pos] = Ma[pos];    return;  }  int mid = (L+R) / 2;  build(L, mid, pos*2);  build(mid+1, R, pos*2 + 1);  Ma[pos] = max(Ma[pos*2], Ma[pos*2 + 1]);  Mi[pos] = min(Mi[pos*2], Mi[pos*2 + 1]);}void getResult(int L, int R, int pos, int a, int b) {  if (b < L || a > R) return;  if (a <= L && b >= R) {//。。。    Ma1 = max(Ma1, Ma[pos]);    Mi1 = min(Mi1, Mi[pos]);    return;  }  int mid = (L+R) / 2;  getResult(L, mid, pos*2, a, b);  getResult(mid+1, R, pos*2 + 1, a, b);}int main() {  int N, M;  scanf("%d%d", &N, &M);  build(1, N, 1);  int m, n;  while (M--) {    scanf("%d%d", &m, &n);    Ma1 = 0; Mi1 = 100000000;    getResult(1, N, 1, m, n);    printf("%d\n", Ma1-Mi1);  }  return 0;}
   

1.怎么用数组设置一颗线段树呢（用数组tree[40]）

a) 规定根结点为v,则左子树为2*v，右子树为2*v+1(通常2*v在代码中写成v<<1 。2*v+1写成v<<1|1 )

2.假设原始数组A[10] = {0, 1, 2, 3, 4, 5, 6, 7 ,8 ,9, 10};

a) 代码一：

建树

void build(int L, int R, int pos) {//L = 1、R = 9、pos = 1为当前位置（L,R代表原数组A的长度从1开始）  if (L == R) {    tree[pos] =A[L];//到达叶子结点时即底部    return;  }  int mid = (L+R)>>1;  build(L, mid, pos<<1);//左子树  build(mid+1, R, pos<<1|1);//右子树  tree[pos] = tree[pos<<1] + tree[pos<<1|1];//父节点的保存两子节点的和}

b)  代码二：

节点修改void updata(int L, int R, int value, int pos, int pos2) {//L = 1、R = 9、value为要增加的值、pos为当前位置、pos2为要修改的节点  if (L == R) {    tree[pos] += value;//到达叶子    return;  }  int mid = (L+R)>>1;  if (pos <= mid) updata(L, mid, value, pos<<1, pos2);//查看该修改节点是否在左子树  else updata(mid+1, R, value, pos<<1|1, pos2);//或者是否在右子树  tree[pos]=tree[pos<<1] + tree[pos<<1|1];//父节点更新两子节点的和}

c)  代码三：

区间查询void interval(int L, int R, int L1, int Rl, int pos) {//求一个区间的和//L,R为所求区间，（L1,R1代表原数组A的长度从1开始）pos代表当前位置  if (L1 <= L && R1 >= R) {    return tree[pos];//返回在该区间内的区间的值   }  int mid = (L1+R1)>>1;  int sum = 0;  if (L1 <= mid) sum += interval(L, R, L1, mid, pos<<1);//在该区间内就递归   if (R1 > mid) sum += interval(L, R, mid+1, R1, pos<<1|1);//在该区间内就递归   return sum; }

  d)  代码四（完整代码）：

#include
   
    int A[15] = {0, 1, 2, 3, 2, 5, 7, 7, 8};int tree[40];void build(int L, int R, int pos) {//L = 1、R = 10、pos为当前位置  if (L == R) {    tree[pos] = A[L];//到达叶子结点时    return;  }  int mid = (L+R)>>1;  build(L, mid, pos<<1);//左子树  build(mid+1, R, pos<<1|1);//右子树  tree[pos] = tree[pos<<1] + tree[pos<<1|1];//父节点的保存两子节点的和}void updata(int L, int R, int value, int pos, int pos2) {  if (L == R) {    tree[pos] += value;    return;  }  int mid = (L+R)>>1;  if (pos <= mid) updata(L, mid, value, pos<<1, pos2);  else updata(mid+1, R, value, pos<<1|1, pos2);  tree[pos] = tree[pos<<1] + tree[pos<<1|1];} int interval(int L, int R, int L1, int R1, int pos) {//求一个区间的  if (L <= L1 && R1 <= R) {    return tree[pos];//返回在该区间内的区间的值   }  int mid = (L1+R1)>>1;  int sum = 0;  if (L <= mid) sum += interval(L, R, L1, mid, pos<<1);//在该区间内就递归   if (R > mid) sum += interval(L, R, mid+1, R1, pos<<1|1);//在该区间内就递归   return sum; }int main() {  build(1, 7, 1);  printf("%d\n", interval(1, 4, 1, 7, 1));  return 0;}
   

如果有不同的可以去这里http://blog.csdn.net/zearot/article/details/48299459

转载地址：https://blog.csdn.net/ZWHSOUL/article/details/72855950 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！