中国高级数据结构领导者，唐氏线段树！【雾

其实并不是，下面即将介绍的是不会TLE的正版线段树哦

引言

在线段树之前我们已经学习过了多中维护区间操作的技巧与数据结构。

  • 维护区间最值:ST表
  • 区间更改转化为单点更改:差分数组
  • 区间和:前缀和

但是，它们有一个共同的缺点，就是更适合离线操作，一旦操作与查询为动态的，它们的时间复杂度就会变成

于是，我们开心的迎来了，线段树——SegmentTree\mathfrak {Segment Tree}

定义

摘自百度百科

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。 使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN)O(logN)。而未优化的空间复杂度为2N2N，因此有时需要离散化让空间压缩。

简而言之

线段树会让你的动态区间操作不会TLE。有时会MLE

具体构成

对于这个二叉树，每一个节点可以维护一段[L,R][L,R]的区间内的信息，而对于它的左儿子，维护的是[L,⌊R2⌋][L,\lfloor \frac{R}{2} \rfloor]这段区间中的信息，右儿子则维护的是[⌊R2⌋+1,R][\lfloor \frac{R}{2} \rfloor + 1,R]这段区间内的信息。

Lazy Mark

当我们对区间进行操作的时候，我们需要修改这段区间对应的所有后代的信息（因为他们算是这段区间的子集），但是我们并不需要对于每次操作都这样修改，因为有些时候我们并不会使用到它的后代记录的区间信息。 就这样，Lazy Mark（懒标记）应运而生。

void cover(long long delta) {
    sum += delta * (r - l + 1);
    tag += delta;
}
void pushDown() {
    if (tag) {
        lc->cover(tag);
        rc->cover(tag);
        tag = 0;
    }
}
//下放标记只下放一次，再向下查询再下放

POJ3468

#include <cstdio>
#include <cstring>
#include <climits>
#include <algorithm>
#include <new>
const int MAXN = 200000;
template<size_t SIZE>
struct MemoryPool {
    char buf[SIZE], *cur;
    MemoryPool(): cur(buf) {}
    void init() {
        cur = buf;
    }
    void *alloc(const int &size) {
        char *p = cur;
        cur += size;
        return p;
    }
};
MemoryPool<(4 + 4 + 8 + 8 + 8 + 8) * MAXN * 5> pool;
struct SegmentTree {
    int l, r;
    SegmentTree *lc, *rc;
    long long sum, tag;
    SegmentTree(int l, int r, SegmentTree *lc, SegmentTree *rc): l(l), r(r), lc(lc), rc(rc), sum(0), tag(0) {}
    void cover(long long delta) {
        sum += delta * (r - l + 1);
        tag += delta;
    }
    void pushDown() {
        if (tag) {
            lc->cover(tag);
            rc->cover(tag);
            tag = 0;
        }
    }
    void update(int l, int r, long long x) {
        if (l > this->r || r < this->l) return;
        else if (l <= this->l && r >= this->r) cover(x);
        else pushDown(), lc->update(l, r, x), rc->update(l, r, x), sum = lc->sum + rc->sum;
    }
    long long querySum(int l, int r) {
        if (l > this->r || r < this->l) return 0;
        else if (l <= this->l && r >= this->r) return sum;
        else return pushDown(), lc->querySum(l, r) + rc->querySum(l, r);
    }
} *root;
SegmentTree *build(int l, int r) {
    if (l == r) return new (pool.alloc(sizeof(SegmentTree))) SegmentTree(l, r, NULL, NULL);
    else {
        int mid = l + (r - l) / 2;
        return new (pool.alloc(sizeof(SegmentTree))) SegmentTree(l, r, build(l, mid), build(mid + 1, r));
    }
}
int main() {
    int n, m;
    while (scanf("%d %d", &n, &m) != EOF) {
        root = NULL;
        pool.init();
        root = build(1, n);
        for (int i = 1; i <= n; i++) {
            long long x;
            scanf("%lld", &x);
            root->update(i, i, x);
        }
        char s[2];
        for (int i = 1; i <= m; i++) {
            scanf("%s", s);
            if (s[0] == 'Q') {
                int a, b;
                scanf("%d %d", &a, &b);
                printf("%lld\n", root->querySum(a, b));
            } else if (s[0] == 'C') {
                int l, r;
                long long x;
                scanf("%d %d %lld", &l, &r, &x);
                root->update(l, r, x);
            }
        }
    }
    return 0;
}

入门题

  • Codevs1080,1081,1082(线段树联系1，2，3)
  • 忠诚，忠诚S %唐氏线段树
  • 数轴染色
  • 借教室(常数大，需要内存池优化)

Powered by Sulfur6\mathfrak {Powered\ by\ Sulfur6}