首页 > 编程语言 >[算法学习笔记] 线段树

[算法学习笔记] 线段树

时间：2024-04-04 11:44:06浏览次数：29  
标签：pr int 线段 tree 笔记 算法 区间 ll pl

前言

线段树可以维护一系列区间问题。包括但不限于区间加，区间乘，区间最值等。

本文主要介绍最基础的区间修改区间查询。你可以认为是 模板 线段树 的解析。

本文将持续更新。

例题

给定一个数列，需要支持如下两种操作：

\(1\) \(x\) \(y\) \(k\) 将区间 \([x,y]\) 中每一个数加 \(k\) .

\(2\) \(x\) \(y\) 查询区间 \([x,y]\) 的和.

\(1\le n,m\le 10^5\)

容易发现，若本题区间修改和区间查询操作分离，可以使用前缀和查分解决。但当区间修改和查询操作混在一起时，显然前缀和无法解决问题。

Description

线段树是一棵平衡二叉树，在本题中，每个节点存储了区间 \([l,r]\) 的和。左儿子和右儿子分别存储 \([l,mid]\)，\([r,mid]\) 的和。(\(mid = (l+r)\div 2\)).

build

容易发现，线段树的建立可以递归进行。线段树的 root 定义为区间 \([1,n]\) 的区间和。参考代码如下：

build 操作 
void build(ll l,ll r,ll p) // l,r 表示当前区间；p表示当前节点编号，参考二叉树的建立。
{
    if(l == r) // 到达叶子赋值
    {
        tree[p] = a[l];
        return;
    }
    ll mid = (l+r) / 2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    tree[p] = tree[p*2] + tree[p*2+1]; // 回溯统计区间和
}

modify

这里引入“懒标记” 的概念（即 lazy tag），可以理解为懒惰修改。

我们在 “堆优化 dijkstra” 中，使用了懒惰修改。由于 priority_queue 不支持随机删除，每次松弛结束的点我们可以打上一个 tag，再次访问时可以直接 continue。

线段树中的 lazy tag 可以类比理解。具体地，对于区间 \([L,R]\) 的修改，朴素做法是不断递归，复杂度太高无法接受。若设当前访问区间为 \([l,r]\) ，当满足 \(l\geq L\) 且 \(r \le R\) 时，也就是区间 \([l,r]\) 是区间 \([L,R]\) 的子集。直接修改即可。同时标记当前区间的所有值均需修改。不必向下递归修改。

反之，当区间 \([l,r]\) 去区间 \([L,R]\) 有交集。我们不得不将区间 \([l,r]\) 拆分，递归求解。此时将区间的 lazy tag 下放。我们只下方一层即可，等后期需要的时候再继续下放。

别忘了将原区间的 lazy tag 删除，因为已经下放到子节点，避免重复修改。

参考代码如下

modify 操作 
void pushdown(ll p,ll len) // 下放 lazy tag操作
{
    mark[p*2] += mark[p];
    mark[p*2+1] += mark[p];
	tree[p*2] += (len-len/2)*mark[p];
    tree[p*2+1] += (len/2)*mark[p];
    mark[p] = 0;  
}

void update(ll l,ll r,ll pl,ll pr,ll p,ll d)
{
    if(pl > r || pr < l) return; //当前区间与所求区间没有交集，不操作
    if(pl >= l && pr <= r) // 当前区间是所求区间的子集，直接修改，标记lazy tag
    {
        tree[p] += (pr-pl+1) * d;
        if(l < r) mark[p] += d;
    }
    else //当前区间与所求区间有交集，将当前区间拆分，递归修改
    {
        ll mid = (pl+pr) / 2;
        pushdown(p,(pr-pl+1)); // 下放 lazy tag
        update(l,r,pl,mid,p*2,d);
        update(l,r,mid+1,pr,p*2+1,d);
        tree[p] = tree[p*2] + tree[p*2+1]; // 儿子更新完后重新赋值父节点
    }
}

query

查询操作类比区间修改。见代码。

query 操作 
ll query(ll l,ll r,ll pl,ll pr,ll p)
{
    if(pl > r || pr < l) return 0;
    if(pl >= l && pr <= r) return tree[p]; // 当前区间是所求区间的子集，直接返回值
    else
    {
        ll mid = (pl+pr) / 2;
        return query(l,r,pl,mid,p*2) + query(l,r,mid+1,pr,p*2+1); // 直接递归查询
    }
}

以上是区间修改区间查询操作，完整代码如下.

区间修改，区间查询模板 
#include <iostream>
#include <cstdio>
#include <algorithm>
#define ll long long
#define N 1000010
using namespace std;
ll tree[N];
ll mark[N];
ll a[N];
ll n,m;
void pushdown(ll p,ll len)
{
    mark[p*2] += mark[p];
    mark[p*2+1] += mark[p];
	tree[p*2] += (len-len/2)*mark[p];
    tree[p*2+1] += (len/2)*mark[p];
    mark[p] = 0;  
}
void build(ll l,ll r,ll p)
{
    if(l == r)
    {
        tree[p] = a[l];
        return;
    }
    ll mid = (l+r) / 2;
    build(l,mid,p*2);
    build(mid+1,r,p*2+1);
    tree[p] = tree[p*2] + tree[p*2+1];
}
void update(ll l,ll r,ll pl,ll pr,ll p,ll d)
{
    if(pl > r || pr < l) return;
    if(pl >= l && pr <= r)
    {
        tree[p] += (pr-pl+1) * d;
        if(l < r) mark[p] += d;
    }
    else
    {
        ll mid = (pl+pr) / 2;
        pushdown(p,(pr-pl+1));
        update(l,r,pl,mid,p*2,d);
        update(l,r,mid+1,pr,p*2+1,d);
        tree[p] = tree[p*2] + tree[p*2+1];
    }
}
ll query(ll l,ll r,ll pl,ll pr,ll p)
{
    if(pl > r || pr < l) return 0;
    if(pl >= l && pr <= r) return tree[p];
    else
    {
        ll mid = (pl+pr) / 2;
        pushdown(p,(pr-pl+1));
        return query(l,r,pl,mid,p*2) + query(l,r,mid+1,pr,p*2+1);
    }
}
int main()
{
    scanf("%lld%lld",&n,&m);
    for(ll i=1;i<=n;i++)
    {
        scanf("%lld",&a[i]);
    }
    build(1,n,1);
    for(ll i=1;i<=m;i++)
    {
        ll flg,x,y,z;
        scanf("%lld",&flg);
        if(flg == 1)
        {
            scanf("%lld%lld%lld",&x,&y,&z);
            update(x,y,1,n,1,z);
        }
        else
        {
            scanf("%lld%lld",&x,&y);
            printf("%lld\n",query(x,y,1,n,1));
        }
    }
}

进阶操作

Warning: 在了解进阶操作前，读者需确保理解上文内容.

1. 区间加乘

模板 线段树2

Description

如题，已知一个数列，你需要进行下面三种操作：

  • 将某区间每一个数乘上 \(x\)；
  • 将某区间每一个数加上 \(x\)；
  • 求出某区间每一个数的和。

同样使用线段树维护区间值，只是在 pushdown 和 modify 操作中，需要注意优先级。必须确保 “先乘后加”。

image
（摘自算法学习笔记 线段树Trick）

然后就是常规的线段树写法，区间加和区间乘是两个独立的 lazy tag，显然。

参考代码 
#include <iostream>
#include <cstdio>
#include <algorithm>
#include <vector>
#define ll long long
#define lc p<<1
#define rc p<<1|1
using namespace std;
const int N = 100005;
struct Node
{
    ll v,lz1=1,lz2;
}tree[N<<2];
int n,q,m;
int a[N];
void build(int l,int r,int p)
{
    if(l == r) 
    {
        tree[p].v = a[l];
        return;
    }
    int mid = (l+r) / 2 ;
    build(l,mid,lc);
    build(mid+1,r,rc);
    tree[p].v = tree[lc].v + tree[rc].v;
}
void pushdown(int p,int l,int r)
{
    int mid=l+r>>1;
    ll &lz1=tree[p].lz1,&lz2=tree[p].lz2;
	if(lz1!=1){
		tree[lc].lz2=tree[lc].lz2*lz1%m;
        tree[rc].lz2=tree[rc].lz2*lz1%m;
		tree[lc].lz1=tree[lc].lz1*lz1%m;
        tree[rc].lz1=tree[rc].lz1*lz1%m;
		tree[lc].v=tree[lc].v*lz1%m;
        tree[rc].v=tree[rc].v*lz1%m;
		lz1=1;
	}
	if(lz2){
		tree[lc].v=(tree[lc].v+(mid-l+1)*lz2)%m;
        tree[lc].lz2=(tree[lc].lz2+lz2)%m;
		tree[rc].v=(tree[rc].v+(r-mid)*lz2)%m;
        tree[rc].lz2=(tree[rc].lz2+lz2)%m;
		lz2=0;
	}
}
void update1(int l,int r,int pl,int pr,int d,int p)
{
    if(pl > r || pr < l) return;
    if(pl >= l && pr <= r)
    {
        tree[p].lz1 = tree[p].lz1 * d % m;
        tree[p].lz2 = tree[p].lz2 * d % m;
        tree[p].v = (tree[p].v *d) % m;
        return;
    }
    int mid = (pl+pr) >> 1;
    pushdown(p,pl,pr);
    update1(l,r,pl,mid,d,lc);
    update1(l,r,mid+1,pr,d,rc);
    tree[p].v = tree[lc].v + tree[rc].v;
}
void update2(int l,int r,int pl,int pr,int d,int p)
{
    if(pl > r || pr < l) return;
    if(pl >= l && pr <= r)
    {
        tree[p].lz2 = (tree[p].lz2 + d) % m;
        tree[p].v = (tree[p].v + (pr-pl+1)*d) % m;
        return;
    }
    int mid = (pl+pr) >> 1;
    pushdown(p,pl,pr);
    update2(l,r,pl,mid,d,lc);
    update2(l,r,mid+1,pr,d,rc);
    tree[p].v = (tree[lc].v + tree[rc].v) % m;
}
long long query(int l,int r,int pl,int pr,int p)
{
    if(pl > r || pr < l) return 0;
    if(pl >= l && pr <= r)
    {
        return tree[p].v;
    }
    int mid = (pl+pr) >> 1;
    pushdown(p,pl,pr);
    return (query(l,r,pl,mid,lc) + query(l,r,mid+1,pr,rc))%m;
}
int main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    cin>>n>>q>>m;
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }   
    build(1,n,1);
    while(q--)
    {
        int flg,x,y,k;
        cin>>flg;
        if(flg == 1) 
        {
            cin>>x>>y>>k;
            update1(x,y,1,n,k,1);
        }
        if(flg == 2)
        {
            cin>>x>>y>>k;
            update2(x,y,1,n,k,1);
        }
        else if(flg == 3)
        {
            cin>>x>>y;
            cout<<query(x,y,1,n,1)<<endl;
        }
    }
    return 0;
}

标签：pr,int,线段,tree,笔记,算法,区间,ll,pl
From： https://www.cnblogs.com/SXqwq/p/18114026

相关文章

  • 完美世界一面 暑期 推荐算法 4.3
    1.code最长公共子序列，不仅要求长度，还要求出其中任意一个序列是什么，秒了2.项目详细问项目，没有扣非常细的细节有了解过双塔模型的结构吗为什么不能user和item提前交叉，那这个缺点，有什么方式可以改进吗双塔模型线上服务是怎样的3.八股Transformer架构，encoder和decoder有什......
  • 数据结构——线段树
    本来是想先写树状数组的，但想到要在树状数组里面用到这篇文章，就先写这个了。线段树的思想线段树是在用一颗树存一个数组中的所有数以及他们所有的2的次方数长度的区间，具体样子如下：                      [1~8]     ......
  • 【算法】递归
    递归的本质是方法不断调用本身。我们知道for循环、while循环都是在代码块内部实现的，而在递归循环中，循环的是一个方法，即让方法不断自我循环。但是不断循环会不断入栈，导致栈溢出。为了解决这个问题，我们首先了解如何实现一个栈。1、明确该递归的参数和返回值。2、确定递归条......
  • 【算法】堆排序
    完全二叉树在学习堆排序之前，我们先对完全二叉树有一个基本的了解。构建过程：数据从上到下，从左到右依次进行构建。我们给出以下数据 我们构建出以下完全二叉树我们观察每个节点的下标，会发现以下规律。 N[i]的左子树：N[2i+1] N[i]的右子树：N[2i+2] N[i]的父节点：N......
  • 面试了微软 bing 应用组大模型算法岗，被自己菜哭了。。。
    节前，我们组织了一场算法岗技术&面试讨论会，邀请了一些互联网大厂朋友、参加社招和校招面试的同学，针对大模型技术趋势、大模型落地项目经验分享、新手如何入门算法岗、该如何备战、面试常考点分享等热门话题进行了深入的讨论。合集在这里：《大模型面试宝典》(2024版)正式发......
  • Python常用算法思想--总概篇
    算法的起源：欧几里德的《几何原本》中阐述的求两个数的最大公约数的过程。算法的定义：解题方案的准确而完整的描述，是一系列解决问题的清晰指令，算法代表用系统的方法描述解决问题的策略机制。算法的本质：算法是程序的灵魂，也是衡量一位程序员水平高低的最好参照物。算法的表示方......
  • SpringMVC学习笔记
    1、概述基于java实现的实现mvc模型的轻量级web框架SpringMVC是一种表现层的框架技术，用于web层的功能开发，是对Servlet进行的封装主要的作用是接收请求和数据，响应结果，所以如何处理请求和响应是SpringMVC的重点​ 之前的开发将后端服务器Servlet拆分成三层，分别是web、service......
  • 神经网络算法：一文搞懂 Self-Attention 和 Multi-Head Attention
    随着Transformer模型的迅速普及，Self-Attention（自注意力机制）和Multi-HeadAttention（多头注意力机制）成为了自然语言处理(NLP)领域中的核心组件。本文将从简要介绍、工作流程、两者对比三个方面，为您解析这两种注意力机制。前期分享一文搞懂Transformer一文搞懂Attent......
  • 神经网络算法：一文搞懂BERT（基于Transformer的双向编码器）
    本文将从BERT的本质、BERT的原理、BERT的应用三个方面，带您一文搞懂BidirectionalEncoderRepresentationsfromTransformers|BERT。GoogleBERT一、BERT的本质BERT架构：一种基于多层Transformer编码器的预训练语言模型，通过结合Tokenization、多种Embeddings和特定任......
  • 数据结构与算法
    1.1数据结构的研究内容程序=数据结构+算法  ———程序的本质 例1：图书管理系统操作对象：若干行数据记录操作算法：查询、插入、删除、修改等操作对象之间的关系：线性关系数据结构：线性数据结构、线性表例2：文件系统的结构图如图可以看到，这是一个典型的树型结构问题，数据......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99