线段树

标签：__ index right 线段 mid long left

title: 线段树
tags: 算法
date: 2022-11-15 10:37:17

本文章遵守知识共享协议 CC-BY-NC-SA ，转载时须在文章的任一位置附上原文链接和作者署名（rickyxrc）。推荐在我的个人博客阅读。

update:2022/12/6 更新了一道例题。

线段树(Segumentosui)，是一种高效的区间查询/修改数据结构，可以快速进行以下操作:

单点加/减
区间加/减
单点查询
区间查询

时间复杂度为O(log n)。

注意事项

线段树查询时，懒标记一定要先下放。
懒标记下放时，当前节点新增值=标记值*节点长度。
线段树最大空间应为maxn的至少4倍。

存储

留个图片的位置 - 存储位置原理图

在线段树中，整体结构采用类似于堆的顺序存储，因此封装常用函数:

long long data[maxn], lazy[maxn];
int n, m, size;
inline long long __lc(long long i) { return i << 1; }
inline long long __rc(long long i) { return __lc(i) | 1; }
void update(long long __index)
{
    data[__index] = data[__lc(__index)] + data[__rc(__index)]; // 更新和
}
void setLazy(long long index, long long value, long long l, long long r)
{
    if (index > size)
        return;
    data[index] += value * (r - l + 1); // 值*长度
    lazy[index] += value; // 懒标记防止向下更新
}
void updateLazy(long long index, long long l, long long r)
{
    int mid = (l + r) >> 1;
    setLazy(__lc(index), lazy[index], l, mid); // 左子树更新
    setLazy(__rc(index), lazy[index], mid + 1, r); // 右子树更新
    lazy[index] = 0; // 清除懒标记
}

然后一个一个满足上述操作。

实现

初始化

通过二分，将每个L=R区间的值初始化，然后向上递归更新非叶子节点的值。

void initSegmentTree(long long left, long long right, long long *initialData, long long __index = 1)
{
    if (right == -114)
        right = n - 1;
    if (left == right)
    {
        data[__index] = initialData[left];
        size = __index > size ? __index : size;
        return;
    }
    long long mid = (left + right) >> 1;
    initSegmentTree(left, mid, initialData, __lc(__index)); // 左子树更新
    initSegmentTree(mid + 1, right, initialData, __rc(__index)); // 右子树更新
    update(__index); // 更新和
}

单点加/区间加

先通过二分，搜索到L,R的区间，然后懒标记增加。

void updateSegment(long long left, long long right, long long value, long long __l = 1, long long __r = -114, long long __index = 1)
{
    if (__r == -114)
        __r = n;
    if (__r < left || __l > right) // 区间不包含
        return;
    if (left <= __l && __r <= right) // 区间包含
    {
        setLazy(__index, value, __l, __r);
        return;
    }
    long long mid = (__l + __r) >> 1;
    updateSegment(left, right, value, __l, mid, __lc(__index)); // 左子树更新
    updateSegment(left, right, value, mid + 1, __r, __rc(__index)); // 右子树更新
    updateLazy(__index, __l, __r); // 懒标记下传
    update(__index); // 重新维护和
}

单点加应该没啥好说的。
实在要说的话，就是updateSegment(x,x,val)。

单点/区间查

与单点加相同的逻辑，只是返回结果并非修改值而已。

long long querySegment(long long left, long long right, long long __l = 1, long long __r = -114, long long __index = 1)
{
    if (__r == -114)
        __r = n;
    updateLazy(__index, __l, __r);
    if (__r < left || __l > right)
        return 0;
    if (left <= __l && __r <= right)
        return data[__index];
    long long mid = (__l + __r) >> 1;
    long long sum = 0;
    sum += querySegment(left, right, __l, mid, __lc(__index));
    sum += querySegment(left, right, mid + 1, __r, __rc(__index));
    return sum;
}

例题

目前这里只有一些纯模板可以解决的题目（姑且算作多倍经验吧），之后如果刷到相同内容会更新。

P3372-【模板】线段树-1

P3374-【模板】树状数组-1

P3368-【模板】树状数组-2

P2068-统计和

P2357-守墓人

P1816-忠诚

P1198-[JSOI2008]-最大数

P1531-I-Hate-It

都是练模板熟练度的题，这里放到一起。

P1438-无聊的数列

这道题很有意思。

首先看题面：加上一个等差数列。

那么仔细想想：是不是可以使用差分和前缀和来解决这道题呢？

scanf("%lld%lld",&n,&m);
for(int i=1;i<=n;i++)
    scanf("%lld",&li[i]);
for(int i=n;i;i--)
    li[i] = li[i]-li[i-1];
initSegmentTree(1,n,1);

for(int i=1;i<=m;i++){	
    scanf("%lld",&mode);
    if(mode==1){
        scanf("%lld%lld%lld%lld",&l,&r,&k,&d);
        updateSegment(l,l,k); // 首项
        updateSegment(l+1,r,d); // 末项
        updateSegment(r+1,r+1,-(k+d*(r-l))); // 最后一项需要减回去（毕竟是差分）
    }
    if(mode==2){
        scanf("%lld",&x);
        printf("%lld\n",querySegment(1,x)); // 差分的前缀和等于原数组
    }

关于Segumentosui

其实我们机房有个 dalao 有一段时间喜欢用日语来写代码，就把SegmentTree写成了这样。。。

标签：__,index,right,线段,mid,long,left
From： https://www.cnblogs.com/rickyxrc/p/17004214.html