线段树（好像写错了？？）

2018-05-15 本文已影响0人 laochonger

对于原理以及使用，参照这篇博客：https://blog.csdn.net/zearot/article/details/48299459 by 岩之痕

这里就简单介绍一下。

一、点修改： //修改某点为v
* 1：建树 自底向上递推（递归），
* 2：修改 向下查找，直到子树的区间完全被包在修改区间中
* 3：查询 同上

建树

void build(int o, int L, int R) { //o是结点
    if(L == R) {
        scanf("%lld", &A[o]);
        sum[o] = A[o];
        minv[o] = A[o];
        return;
    }
    int m = (L+R) >> 1;
    build(o<<1, L, m);
    build(o<<1 | 1, m+1, R);
    sum[o] = sum[o<<1] + sum[o<<1 | 1];
    minv[o] = min(minv[o<<1], minv[o<<1|1]);
}

修改

void update(int o, int L, int R){//o为结点，L，R为该结点表示的线段 
    int M = L + (R-L)/2;
    if(L == R){
        minv[o] = v; //叶结点，直接更新minv 
         sum[o] = v;
    }else{ //L<R
        //先递归计算左子树或右子树
        if(p <= M) update(o*2, L, M); else update(o*2+1, M+1, R);//p为需要修改的结点 
        //然后计算本结点的minv和sum
        minv[o] = min(minv[o*2], minv[o*2+1]);
        sum[o] = sum[o<<1] + sum[o<<1 | 1]; 
    }
}

查询

int l,r;

int query_min(int o, int L, int R){
    int M = L + (R-L)/2, ans = INF;
    if(l<=L && R <= r) return minv[o];
    if(l <= M)ans = min(ans, query_min(o*2, L,M));
    if(M < r) ans = min(ans, query_min(o*2+1,M+1,R));
    return ans;
}

int query_sum(int o, int L, int R){
    int M = L + (R-L)/2, sum = 0;
    if(l<=L && R <= r) return sum[o];
    if(l <= M)sum += query_sum(o*2, L, M);
    if(M < r) sum += query_sum(o*2+1, M+1, R);
    return sum;
}

二、区间加减：
主要不同就是将sum[o]定义为“如果只执行结点o及其子孙结点中的add操作，结点o对应区间中所有数的和”，即如果结点o所表示线段已经被包含，不需要计算子树的sum[]。另一个不同在于因为前面更新时的简化，需要用一个lazy数组来记录add操作，并为了方便增加了maintain函数来维护值。以下主要以计算sum操作举例。
int v;//加上的值
int l,r;//操作的段
int addv[];//lazy数组
int sum[];//线段和
int _sum;//输出用_sum
memset(addv, 0 ,sizeof(addv));
* 1：建树 自底向上递推（递归），

void build(int o, int L, int R) { //o是结点
    if(L == R) {
        scanf("%lld", &A[o]);
        sum[o] = A[o];
        minv[o] = A[o];
        maxv[o] = A[o];
        return;
    }
    int m = (L+R) >> 1;
    build(o<<1, L, m);
    build(o<<1 | 1, m+1, R);
    sum[o] = sum[o<<1] + sum[o<<1 | 1];
    minv[o] = min(minv[o<<1], minv[o<<1|1]);
    maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);

 *   **2：修改**  向下查找，直到子树的区间完全被包在修改区间中时，修改lazy数组的值

void update(int o, int L, int R) {
    int lc = o*2, rc = o*2+1;
    if(y1 <= L && y2 >= R) { // 标记修改      
      addv[o] += v;//累加边界的add值 
    } else {
      int M = L + (R-L)/2;
      if(y1 <= M) update(lc, L, M);
      if(y2 > M) update(rc, M+1, R);
    }
    maintain(o, L, R);//更新边界结点及其父结点的sum[o]
  }

 *   **3：维护**  通过lazy标记更新sum[o]的值

void maintain(int o, int L, int R) {
    int lc = o*2, rc = o*2+1;
    if(R > L) {//非叶结点
      sumv[o] = sumv[lc] + sumv[rc];
      minv[o] = min(minv[lc], minv[rc]);
      maxv[o] = max(maxv[lc], maxv[rc]);
    }
    if(addv[o]) { minv[o] += addv[o]; maxv[o] += addv[o]; sumv[o] += addv[o] * (R-L+1); }
  }

 *   **4：标记传递** 为了使得在多次更新后仍可以通过addv[o]获得正确的附加信息（实际上可以在maintain中完成，但为了代码的统一性，加此函数）

void pushdown(int o) {
    int lc = o*2, rc = o*2+1;
    if(addv[o]) {
      addv[lc] += addv[o];
      addv[rc] += addv[o];
      addv[o] = 0; // 清除本结点标记,防止维护时叠加多次前次的附加信息
    }
  }

 *   **5：查询**  因为范围内的结点o的子结点没更新，所以需要用lazy数组在查询sum的时候更新输出的值（并不改变sum[o]子结点的值）

void query(int o, int L, int R, int add) {
    if(y1 <= L && y2 >= R) {//递归边界，用边界区间的附加信息更新答案
      _sum += sumv[o] + add * (R-L+1);
      _min = min(_min, minv[o] + add);
      _max = max(_max, maxv[o] + add);
    } else {//递归统计，累加参数add
      int M = L + (R-L)/2;
      if(y1 <= M) query(o*2, L, M, add + addv[o]);
      if(y2 > M) query(o*2+1, M+1, R, add + addv[o]);
    }
  }

三、区间修改：
与前面不一样，set操作具有“顺序”的属性，所以我们要让任意两个set操作不会存在祖先-后代关系。且当上一次的set操作边界可能在下一次set时需要向下更新，比如上一次有[4，5]（结点2）改为了1，但是下一次要求改[5,6]为2，此时需要将结点2的左子结点4置为4，将右结点置为2，故pushdown函数其实是在此种情况下起作用。
memset（set，-1， sizeof(set)）；

1：建树 自底向上递推（递归），

void build(int o, int L, int R) { //o是结点
    if(L == R) {
        scanf("%lld", &A[o]);
        sum[o] = A[o];
        maxv[o] = A[o];
        minv[o] = A[o];
        return;
    }
    int m = (L+R) >> 1;
    build(o<<1, L, m);
    build(o<<1 | 1, m+1, R);
    sum[o] = sum[o<<1] + sum[o<<1 | 1];
    minv[o] = min(minv[o<<1], minv[o<<1|1]);
    maxv[o] = max(maxv[o<<1], maxv[o<<1|1]);

2：修改 向下查找，直到子树的区间完全被包在修改区间中时，修改lazy数组的值;否则pushdown，而后维护。

void update(int o, int L, int R) {
    int lc = o*2, rc = o*2+1;
    if(y1 <= L && y2 >= R) { // 标记修改      
      setv[o] = v; addv[o] = 0; 
    } else {
      pushdown(o);
      int M = L + (R-L)/2;
      if(y1 <= M) update(lc, L, M); else maintain(lc, L, M);//这里需要注意，只要标记下传，就说明该结点的子结点有可能需要更新，所以该子树的附加信息就需要进行重新计算
      if(y2 > M) update(rc, M+1, R); else maintain(rc, M+1, R);//同上，如果这里递归了，那么自然会维护，所以只要维护未进行递归的部分
    }
    maintain(o, L, R);
  }

3：维护 通过lazy标记更新sum[o]的值

void maintain(int o, int L, int R) {
    int lc = o*2, rc = o*2+1;
    if(R > L) {
      sumv[o] = sumv[lc] + sumv[rc];
      minv[o] = min(minv[lc], minv[rc]);
      maxv[o] = max(maxv[lc], maxv[rc]);
    }
    if(setv[o] >= 0) { minv[o] = maxv[o] = setv[o]; sumv[o] = setv[o] * (R-L+1); }
  }

4：标记传递 为了使得在多次更新后仍可以通过set[o]获得正确的附加信息（具体上面已经说过了）

void pushdown(int o) {
    int lc = o*2, rc = o*2+1;
    if(setv[o] >= 0) {//本结点有标记才传递，-1代表没有标记
      setv[lc] = setv[rc] = setv[o];
      addv[lc] = addv[rc] = 0;
      setv[o] = -1; // 清除本结点标记
    }
  }

5：查询 因为范围内的结点o的子结点没更新，所以需要用lazy数组在查询sum的时候更新输出的值（并不改变sum[o]子结点的值）。
这里有一个问题，若是先执行set(2,1,3)再执行set(1,1,8)操作，就违反了任意两个set不存在祖先-后代关系。所以我们规定这种情况下，我们只需要以祖先结点上的操作为准即可。

 void query(int o, int L, int R, int add) {
    if(setv[o] >= 0) {   //递归边界1，有set标记
      int v = setv[o] + add + addv[o];
      _sum += v * (min(R,y2)-max(L,y1)+1);
      _min = min(_min, v);
      _max = max(_max, v);
    } else if(y1 <= L && y2 >= R) {//递归边界2，边界区间
      _sum += sumv[o] ;//此边界没有被任何set操作影响
      _min = min(_min, minv[o] );
      _max = max(_max, maxv[o] );
    } else {           //递归统计
      int M = L + (R-L)/2;
      if(y1 <= M) query(o*2, L, M, add );
      if(y2 > M) query(o*2+1, M+1, R, add);
    }
  }

线段树（好像写错了？？）

猜你喜欢

热点阅读