初级线段树小结

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

　　为了区间的方便书写， 我们常常把线段树的区间取为 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;
}

 

 

　　操作时候的注意事项：

　　1. 随我们我们是 2ⁿ 个元素， 但是我们的线段树区间要求的是 2ⁿ⁺¹ - 1 个； 这个是因为我们的基础元素所处的是叶子,　　他们需要父节点进行记录数值。　　父节点是维护的数据！

　　2. 注意我们的数组是由零开始， 和由 1 开始不同， 他们父节点和左右儿子的所以下表关系有着些许的变化

　　eg :　　由零开始： parent : x  --->  leftson : x / 2 + 1 ； rightson ： x / 2 + 2;

　　　　　　由一开始： parent : x  --->  leftson : x / 2 + 0 ； rightson ： x / 2 + 1;

　　3. 更新的操作是基于叶子节点的操作， 因为要直接定位到叶子节点的位置；

　　4. 我们进行区间的操作的时候， 可以从下标， 来进行推导区间， 但是太繁琐（仅代表个人观点）， 不是直接将区间的范围放入函数的参数当中！　　注意在外部调用时候，需要的是 query(a, b, 0, 0, n);

　　5. 在初始化时候要注意， 他是 n <<= 1;  不要写成了 n>>1; 这个亚子的话是死循环！