线段树的实现与应用

SegmentFault思否 · 公众号 · 程序员 · 2020-02-05 12:00

正文

本文转载于思否社区专栏：算法小木屋

作者：稀有的猪

1. 原理

原理图

懒标记含义：

本节点的统计信息已经根据标记更新过了，但是本节点的子节点仍需要进行更新。即，如果要给一个区间的所有值都加上 1，那么，实际上并没有给这个区间的所有值都加上 1，而是打个标记，记下来，这个节点所包含的区间需要加1.打上标记后，要根据标记更新本节点的统计信息。

2. 存储结构

使用数组存储。
线段树需要的数组元素个数是：

,一般都开 4 倍空间，比如：int A[n<<2];

3. 代码实现1(单点修改，区间查询)

定义

const int N = 100010;
int sum[N << 2];    //4*N的空间
int a[N];    //原数组下标

建树

void build(int u, int l, int r)
  {
    if(l == r)
    {
        sum[u] = a[l];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
  }

更新节点信息

void pushup(int u)
{
  sum[u] = sum[u << 1]  + sum[u << u | 1];
}

单点修改

void modify(int L, int c, int u, int l, int r)
{
    if(l == r)
    {
        sum[u] += c;
        return;
    }
    int mid = l + r >> 1;
    if(L <= mid) modify(L, c, u<< 1, l, mid);
    else modify(L, c, u << 1 | 1, mid + 1, r);
    pushup(u);
}

区间查询

int query(int L, int R, int l, int r, int u)
{
     if( L <= l && r <= R)    return sum[u];

     int mid = l + r >> 1;
     int ans = 0;
     if(L <= mid) ans += query(L, R, l, mid, u << 1);
     if( R > mid) ans += query(L, R, mid +1, r, u << 1 | 1);
     return ans;
}

4. 代码实现2(区间修改，区间查询)

定义

const int N = 100010;

int sum[N << 2];  //求和
int add[N << 2];    //懒惰标记
int a[N];    //原数组
int n; // 原数组中元素的个数

建树

void build(int u, int l, int r)
{
 if(l == r)
 {
     sum[u] = a[l];
     return;
 }
 int mid = l + r >> 1;
 build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
 pushup(u);
}

更新节点信息

void pushup(int u)
{
  sum[u] = sum[u << 1]  + sum[u << u | 1];
}

下推标记

void pushdown(int u, int ln, int rn)
{
   if(add[u])
   {
       //下推标记
       add[u << 1] += add[u];
       add[u << 1 | 1] += add[u];
       //修改子节点的sum使之与对应的add相对应
       sum[u << 1] += add[u] * ln;
       sum[u << 1 | 1] += add[u] * rn;
       //清楚本节点标记
       add[u] = 0;
   }
}