首页 > > 程序设计 > C/C++ >

初级线段树小结

2019-08-26 05:37:18来源：博客园阅读 ()

初级线段树小结

　　线段树是一种高效的维护区间的数据结构，他是通过树的特点，进行了区间的二分法，通过不断地分治、递归，完成了区间数据的高效管理与维护！

　　为了区间的方便书写，我们常常把线段树的区间取为 2 的幂，方便进行区间的二分，与形成一个完美二叉树（与完全二叉树有些许的区别，完全二叉树可以在最后一层中缺少若干节点。）

　　线段树常常会有一下几种操作，包括

　　1.线段树的初始化；（注意初始化过程当中的规模确定，确定线段树的大小）

　　2. 修改某个节点的数值；（修改过程中，需要不断地对区间进行维护）

　　3. 求某段区间的最小值　　（这里说的是维护最小值的线段树，当然递归的话，你也可以维护最大值！）

　　关于以上三种操作的实现：

/*
    在此处我们建立的是维护最小值的线段树, 维护的是其他的话吗，仅仅只需要改一些初始化以及更新的细节点
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <string>
#include <cctype>
#include <algorithm>
#include <vector>
#include <queue>
#include <list>
#include <map>
#include <stack>
#include <set>
using namespace std;

const int INF = 1e8;            // 因为是维护最小值的线段树， 我们初始化当然是最大值
const int MAX = 1 << 17;        // segment tree 最多有这么多节点
int date[MAX*2 - 1];            //  但是还要加一倍减一 ， 是因为它上面还有node
int n;                          //全局变量， 用来表示线段树的规模；
//初始化
void Initial(int n_){           //n_ 是你原本需要数据的规模
    n = 1;
    while(n < n_)   n <<= 1;       // 为了方便， 把线段树的底层规模设置成为了 2 的幂次 ，由n_扩大到了 n !
    printf("N : %d \n", n);
    for(int i = 0; i < 2 * n - 1; i++)  date[i] = INF;
}
//将下标索引k的元素更新为 a; 这里的 K 索引下标是叶子点从0开始输入的数据
void Update(int k, int a){
    k += n - 1;                 //直接定位到叶子节点的位置， 进行更新
    date[k] = a;
    while(k > 0){
        k = (k - 1) / 2;        //定位父节点
        date[k] = min(date[2*k+1], date[2*k+2]);
    }
}
// 求的是区间 [a , b) 当中的维护值， [ l ,r )似的是他在该区间的结果；
// k 是节点的编号， 当然 [l, r) 正是这个节点对应的区间
// 注意点， a , b 的区间不是 在线段树上面的区间； 而是你输入数据的区间
int Query(int a, int b, int k, int l, int r){
    if(r <= a||l >= b)  return INF;     //区间根本不存在交集的情况
    if(a <= l&&b >= r)  return date[k];
    else{   //那就是仅仅只有部分交点的情况
        int x = Query(a, b, 2 * k + 1, l, (l + r) / 2); //左节点
        int y = Query(a, b, 2 * k + 2, (l + r) / 2, r); //右节点
        return min(x, y);
    }
}
int main()
{
    printf("THE START:\n");
    Initial(16);
    printf("THE INITIAL IF FINISHED\n");
    for(int i = 0; i < 16; i++){
        Update(i, 16 - i);
    }
    for(int i = 0; i < 16; i++){
        printf("%d ", 16 - i);
    }
    cout<<endl;
    printf("%d\n", Query(0, 16, 0, 0, 16));
    printf("%d\n", Query(0, 10, 0, 0, 16));
    printf("%d\n", Query(12, 16, 0, 0, 16));
    return 0;
}