脚本宝典收集整理的这篇文章主要介绍了【备忘】线段树，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

防止遗忘，好记性不如烂博文（雾

线段树

_{这年头怎么在哪儿码题都能碰到这玩意儿}

线段树（(text{Segment tree})）可谓是 (text{OIer}) 们的家常便饭，应用于维护区间信息（需满足结合律）。另外别跟我拿树状数组和它比。

从小见大，边看题边学习~

维护区间和

（洛谷 (text{P3372}) 【模板】线段树 (text{1})）

题目描述

已知一个数列，你要进行下面两种操作：

1. 将某区间每一个数加上 (text{x})。
2. 求出区间和。

输入格式

第一行包含两个整数 (text{n, m})，分别表示该数列数字的个数和操作的总个数。

第二行包含 (text{n}) 个用空格分隔的整数，其中第 (text{i}) 个数字表示数列第 (text{i}) 项的初始值。

接下来 (text{m}) 行每行包含 (text{3}) 或 (text{4}) 个整数，表示一个操作，具体如下：

操作 (text{1})： 格式：(text{1 x y k}) 含义：将区间 (text{[x,y]}) 内每个数加上 (text{k})。

操作 (text{2})： 格式：(text{2 x y}) 含义：输出区间 (text{[x,y]}) 内每个数的和。

输出格式

输出包含若干行整数，即为所有操作 (text{2}) 的结果。

基本的建树

线段树是一棵平衡二叉树，根节点维护全区间，然后往下对半分（即每个节点都存了条线段）。不保证岁有的区间都是线段树的节点。当然还要依题存区间和啊什么的值。

编号为 (text{k}) 的节点，左右儿子节点编号分别为 (text{k << 1, k << 1 | 1})，若节点 (text{k}) 存储区间 (text{[l,r]}) 的和，则左右儿子节点分别存储区间 (text{[l, mid]}) 和 (text{mid + 1, r}) 的和，其中 (text{mid = l + r >> 1})，左节点存储区间长度，与右节点相同或多 (text{1})。

递归建立线段树：

void build (int l, int r, int p) {
    if (l == r) { // 叶子结点
        t[p] = a[l]; // 直接取数组值
        return ;
    }
    int mid = l + r >> 1;
    build (l, mid, p << 1);
    build (mid + 1, r, p << 1 | 1); // 建立儿子节点
    t[p] = t[p << 1] + t[p << 1 | 1]; // 本节点值为儿子节点和
}
@H_184_126@
区间修改
引入懒标记，朴素想法为使用递归一层层修改，但复杂度较高。使用懒标记后，对于恰好是线段树节点的区间，直接打上标记，不用递归，等用到他的子区间时，向下传递。
void upd (int cl, int cr, int d, int p = 1, int l = 1, int r = n) {
	// 参数意义：最初修改的区间，修改值，当前分出来的区间所在的节点
    if (l > cr or r < cl) { // 区间无交集
        return ;
    }
    if (l >= cl and r <= cr) {
        // 直接在区间节点上加，其实换成 == 没影响
        t[p] += (r - l + 1) * d;
        if (r > l) tag[p] += d;
        return ;
    }
    int mid = l + r >> 1;
    tag[p << 1] += tag[p]; // 传递标记
    tag[p << 1 | 1] += tag[p];
    t[p << 1] += tag[p] * (mid - l + 1);
    t[p << 1 | 1] += tag[p] * (r - mid); // 向下更新
    tag[p] = 0; // 清除标记
    upd (cl, cr, d, p << 1, cl, mid);
    upd (cl, cr, d, p << 1 | 1, mid + 1, r); // 重复步骤，继续向下更新
    t[p] = t[p << 1] + t[p << 1 | 1]; //更新当前节点
}

中间有一段常被习惯性地封装：
inline void push_down (int p, int len) {
    tag[p << 1] += tag[p]; // 传递标记
    tag[p << 1 | 1] += tag[p];
    t[p << 1] += tag[p] * (len - len / 2);
    t[p << 1 | 1] += tag[p] * (len / 2); // 向下更新
    tag[p] = 0; // 清除标记
}

然后直接在 (text{upd}) 函数里调用：
push_down (p, r - l + 1);

单点修改。。。让修改区间左右端点相等即可。
区间查询
跟上面差不多
int query (int ql, int qr, int p = 1, int l = 1, int r = n) {
    if (l > qr or r < ql) return ;
    if (ql <= l and qr >= r) return t[p];
    int mid = l + r >> 1;
    push_down (p, r - l + 1);
    return query (ql, qr, p << 1, l, mid) +
    query (ql, qr, p << 1 | 1, mid + 1, r);
}


没了。
实际上线段树还可以维护区间最值、区间 (text{gcd}) 等等，操作除了区间加也可以是区间乘、区间赋值，了解原理后很容易改。
脚本宝典总结
       
以上是脚本宝典为你收集整理的【备忘】线段树全部内容，希望文章能够帮你解决【备忘】线段树所遇到的问题。
		
如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。
		
本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。