跳转至

线段树

线下模版

  • 节点到底维护什么(Info)

    区间和/区间最值/...

  • 懒惰标记是什么(Tag)

    加一个数/覆盖/...

  • 标记怎么作用在节点上(Apply)

// 需要根据题目变动的地方
struct SegTree {
    vector<i64> sum, lazy, len;

    // 1. push_up 子节点信息->父节点信息
    void push_up(int p) {
        sum[p] = sum[p * 2] + sum[p * 2 + 1];   
    }

    // 2. apply 将懒标记作用于当前节点Info
    void apply(int p, i64 lz) {
        sum[p] += len[p] * lz; 
        lazy[p] += lz;
    }

    // 3. push_down 将当前节点的懒标记下放给左右儿子
    void push_down(int p) {
        if (lazy[p]) {
            apply(p * 2, lazy[p]);
            apply(p * 2 + 1, lazy[p]);
            lazy[p] = 0; // 清空自己的标记
        }
    }

    #define lson self(self, p * 2, l, mid)
    #define rson self(self, p * 2 + 1, mid + 1, r)
    int n;
    seg_tree(const vector<int> &a) {
        n = a.size() - 1; // 原数组0空着
        sum.resize(n * 4);
        len.resize(n * 4);
        lazy.resize(n * 4);
        auto build = [&](auto &self, int p, int l, int r) {
            if (l == r) {
                sum[l] = a[l];
                len[p] = 1;
                return; 
            }
            int mid = (l + r) >> 1;
            lson, rson;
            push_up(p);
        };
        build(build, 1, 1, n);
    }
    void update(int L, int R, i64 val) {
        auto _update = [&](auto &self, int p, int l, int r) {
            if (L <= l && r <= R) {
                apply(p, val);
                return;
            }
            push_down(p);

            int mid = (l + r) >> 1;

            if (L <= mid) lson;
            if (R > mid) rson;

            push_up(p);
        };
        _update(_update, 1, 1, n);
    }

    i64 query(int L, int R) {
        auto _query = [&](auto &self, int p, int l, int r) {
            if (L <= l && r <= R) return sum[p];

            push_down(p);

            int mid = (l + r) >> 1;
            if (R <= mid) return lson;
            if (L > mid) return rson;
            return lson + rson;
        };
        return _query(_query, 1, 1, n);
    }
};

使用结构体封装的线段树的写法

  • 模块1 状态定义

成员变量：

  1. 维护的核心信息，例如vector<i64> sum维护区间和
  2. 辅助信息，处理lazy, tag时用到，例如：vector<int> len

  3. 懒标记，记录对当前区间所有元素统一加上的值

  4. 模块2 单节点核心操作

1.核心信息会怎么从下向上合并

void push_up(int p) {
  sum[p] = sum[2 * p] + sum[2 * p + 1];
  len[p] = len[2 * p] + len[2 * p + 1]; // len也可以直接在build里建好，不用每次算
}
push_up就是负责儿子更新父亲的，只要儿子更新，退栈时必定会push_up

2.apply给节点p打上标记，立即更新节点信息

apply是从push_down里再抽出来的

功能就是把lz作用在p上

void apply(int p, i64 lz) {
  sum[p] += lan[p] * lz;
  lazy[p] += lz;
}

3.push_down父亲怎么把懒标记分给儿子

void push_down(int p) {
  if (lazy[p]) {
    apply(p * 2, lazy[p]);
    apply(p * 2 + 1, lazy[p]);
    lazy[p] = 0;
  }
}
  • 模块3 树上漫游
int n;
#define lson self(self, p * 2, l, mid)
#define rson self(self, p * 2, mid + 1, r)

seg_tree(const vector<int> &a) {
  n = a.size() - 1;
  // 給各数组初始化大小
  // sum.resize(4 * n);
  // ...
  auto build = [&](auto& self, int p, int l, int r) {
    if (l == r) {
      sum[p] = a[l];
      len[p] = 1;
      return;
    }
    int mid = (l + r) >> 1;
    lson, rson;
    push_up(p);
  };
  build(build, 1, 1, n);
}

void update(int L, int R, int c) {
  auto update = [&](auto &self, int p, int l, int r) {
    if (L <= l && r <= R) {
        apply(p, c);
        return;
    }
    // 没有完全包含，就继续往下走
    push_down(p);
    int mid = (l + r) >> 1;
    // 目标区间和哪里有交集，就去哪边
    if (L <= mid) lson;
    if (mid < R) rson;
    // 儿子更新完了，更新自己
    push_up(p);
  };
  update(update, 1, 1, n);
}

i64 query(int L, int R) {
  auto query = [&](auto& self, int p, int l, int r) {
    // 完全包含，直接返回当前答案
    if (L <= l && r <= R) return sum[p];
    // 要往下走了，先清账 push_down
    push_down(p);
    int mid = (l + r) >> 1;
    // 如果之和一边有交集，就之间return单边
    if (R <= mid) return lson;
    if (mid <= L) return rson;
    return lson + rson;
  };
  return query(query, 1, 1, n);
}