基本线段树以及相关例题

1.线段树的概念

线段树是一种二叉树，也就是对于一个线段，我们会用一个二叉树来表示。

这个其实就是一个线段树，我们会将其每次从中间分开，其左孩子就是左边的集合的和，其右孩子就是右边集合的和；

我们可以用一个结构体tree去表示线段树的结点，tree.L代表线段树左边界,tree.R代表线段树的右边界； 

因此我们可以得到一个结论，对于一个节点编号为i的结点，其左孩子的编号为i*2，其右孩子编号为i*2+1；

因此我们可以得到结论：tree[i].sum=tree[i∗2].sum+tree[i∗2+1].sum；

那么首先写出我们的建树代码

//建树代码
void build(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=a[l];
		return ; 
	}
	int mid=l+r>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
//有些题目可能没有最后的加，因为那个可能只是想算叶子结点的最后的值，所以中间的可以不记录，都是0
    tree[i].sum=tree[i∗2].sum+tree[i∗2+1].sum；
}

2 .基本线段树的类型

1.单点修改，区间查询

首先是如何查询呢？

我们可以首先判断查询的是在某个规定的区间（用户输入的）吗？

int cha(int i,int l,int r)//i是编号点，l是规定的左边界，r是右边界
{
    if(tree[i].l>=l && tree[i].r<=r)//如果这个区间被完全包括在目标区间里面，直接返回这个区间的值
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  return 0;//如果这个区间和目标区间毫不相干，返回0
    int s=0;
    if(tree[i*2].r>=l)  
       s+=cha(i*2,l,r);//如果这个区间的左儿子和目标区间又交集，那么搜索左儿子
    if(tree[i*2+1].l<=r)  
       s+=cha(i*2+1,l,r);//如果这个区间的右儿子和目标区间又交集，那么搜索右儿子
    return s;
}

单点修改操作

void add(int i,int dis,int k)//dis目标位置，k要加上的数值
{
	if(tree[i].l==tree[i].r)//如果找到叶子结点，就说明找到了，要在这个位置+k
	{
		tree[i].sum+=k
		return ;
	}
	if(dis<=tree[i*2].r)//当目标位置，在左孩子
	add(2*i,dis,k);
	if(dis>=tree[i*2+1].l)//当目标位置在右孩子
	add(2*i+1,dis,k);
	tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;//更新区间值
	return ;
}

2.区间修改，单点查询 

区间修改：

void add(int i,int l,int r,int k)//l左边界，r右边界，k加的数值
{
	if(tree[i].l>=l&&tree[i].r<=r)//当某个区间在范围内就可以在这个地方做+k的标记
	{
		tree[i].sum+=k;
		return ;
	}
	if(tree[i*2].r>=l)//如果左孩子与目标区间有交集
	add(i*2,l,r,k);
	if(tree[i*2+1].l<=r)//右孩子与目标区间有关系
	add(i*2+1,l,r,k);
}

单点查询：

void cha(int i,int dis)//dis目标值
{
	ans+=tree[i].sum;//把路上做的标记全加上
	if(tree[i].l==tree[i].r)//如果到了叶子结点就停止
	return ;
	if(dis<=tree[i*2].r)//目标值在左孩子
	cha(i*2,dis);
	if(dis>=tree[i*2+1].l)//目标值在右孩子
	cha(i*2+1,dis);
}

 3.区间修改，区间查询

区间修改和区间查询，我们需要一个pushdown函数用于将标记可以推下去，让每一个孩子都能够加上需要加的值，我们当有一个区间符合需要加的时候，先给这个区间做一个lz标记，用于表示这个区间每个数都需要加上lz，用pushdown把标记推下去，证明每个数都需要加上这个值

pushdown函数：

void pushdown(int i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;//左右儿子分别加上父亲的lz，就是给儿子做标记
        tree[i*2+1].lz+=tree[i].lz;
        int mid=(tree[i].l+tree[i].r)>>1;
        tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);//左右分别求和加起来
        tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;//父亲lz归零
    }
    return ;
}

此时我们就是需要在区间修改函数add里面进行pushdown的调用

void add(int i,int l,int r,int k)
{
    if(tree[i].r<=r && tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;//记录lazytage
        return ;
    }
    pushdown(i);//向下传递
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}

同时在区间查询cha函数里面也需要调用这个pushdown

long long cha(int i,int l,int r)
{
    if(tree[i].l>=l && tree[i].r<=r)//如果在对应的区间内就直接加上这部分的和
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  //如果毫无关系，直接跳过
	return 0;
    pushdown(i);//调用
    long long s=0;
    if(tree[i*2].r>=l)  //如果左孩子和这个目标区间有交集
	s+=cha(i*2,l,r);
    if(tree[i*2+1].l<=r)  //右孩子和目标区间有交集
	s+=cha(i*2+1,l,r);
    return s;
}

3.相关例题

1.模版树状数组

题解：这题就是属于区间修改，单点查询的模版题

#include<bits/stdc++.h>
using namespace std;

int n,m;
int t;
int flag;
int a[500005];
int ans;
struct node
{
	int l;
	int r;
	int sum;
}tree[500005*4];

void build(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=a[l];
		return ; 
	}
	int mid=l+r>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
}

void add(int i,int l,int r,int k)
{
	if(tree[i].l>=l&&tree[i].r<=r)
	{
		tree[i].sum+=k;
		return ;
	}
	if(tree[i*2].r>=l)
	add(i*2,l,r,k);
	if(tree[i*2+1].l<=r)
	add(i*2+1,l,r,k);
}

void cha(int i,int dis)
{
	ans+=tree[i].sum;
	if(tree[i].l==tree[i].r)
	return ;
	if(dis<=tree[i*2].r)
	cha(i*2,dis);
	if(dis>=tree[i*2+1].l)
	cha(i*2+1,dis);
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		cin>>flag;
		if(flag==1)
		{
			int x,y,z;
			cin>>x>>y>>z;
			add(1,x,y,z);
		}
		else
		{
			ans=0;
			int x;
			cin>>x;
			cha(1,x);
			printf("%d\n",ans);
		}
	}
	return 0;
}

2.模版线段树1

题解：如果这题用区间修改，单点查询再累加，那么时间会超限的（！！！！！！！）

因此我们要用区间修改，区间查询（一开始没学这个就写了，所以以后一定要先学完，再去尝试写，害我TLE了一次）

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n,m;
int flag;
long long ans=0;
long long a[100005];
struct node
{
	int l;
	int r;
	long long sum;
	long long lz;
}tree[500005];


void build(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
}
 
 void pushdown(int i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;//左右儿子分别加上父亲的lz
        tree[i*2+1].lz+=tree[i].lz;
        int mid=(tree[i].l+tree[i].r)>>1;
        tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);//左右分别求和加起来
        tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;//父亲lz归零
    }
    return ;
}
 
void add(int i,int l,int r,int k)
{
    if(tree[i].r<=r && tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;//记录lazytage
        return ;
    }
    pushdown(i);//向下传递
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}



long long cha(int i,int l,int r)
{
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  
	return 0;
    pushdown(i);
    long long s=0;
    if(tree[i*2].r>=l)  
	s+=cha(i*2,l,r);
    if(tree[i*2+1].l<=r)  
	s+=cha(i*2+1,l,r);
    return s;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		cin>>flag;
		if(flag==1)
		{
			long long x,y,z;
			cin>>x>>y>>z;
			add(1,x,y,z);
		}
		else
		{
			ans=0;
			long long x,y;
			cin>>x>>y;
			ans=cha(1,x,y);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

3.A Simple Problem with Integers

题解：一样是区间修改区间查询，纯纯水题一个，实在不会看第二题

#include <cstdio>
#include <iostream>
#include <queue>
#include <cstring>
using namespace std;
int n,m;
char flag;
long long ans=0;
long long a[100005];
struct node
{
	int l;
	int r;
	long long sum;
	long long lz;
}tree[500005];


void build(int i,int l,int r)
{
	tree[i].l=l;
	tree[i].r=r;
	if(l==r)
	{
		tree[i].sum=a[l];
		return ;
	}
	int mid=l+r>>1;
	build(i*2,l,mid);
	build(i*2+1,mid+1,r);
	tree[i].sum = tree[i * 2].sum + tree[i * 2 + 1].sum;
}
 
void pushdown(int i)
{
    if(tree[i].lz!=0)
    {
        tree[i*2].lz+=tree[i].lz;//左右儿子分别加上父亲的lz
        tree[i*2+1].lz+=tree[i].lz;
        int mid=(tree[i].l+tree[i].r)>>1;
        tree[i*2].sum+=tree[i].lz*(mid-tree[i*2].l+1);//左右分别求和加起来
        tree[i*2+1].sum+=tree[i].lz*(tree[i*2+1].r-mid);
        tree[i].lz=0;//父亲lz归零
    }
    return ;
}
 
void add(int i,int l,int r,int k)
{
    if(tree[i].r<=r && tree[i].l>=l)//如果当前区间被完全覆盖在目标区间里，讲这个区间的sum+k*(tree[i].r-tree[i].l+1)
    {
        tree[i].sum+=k*(tree[i].r-tree[i].l+1);
        tree[i].lz+=k;//记录lazytage
        return ;
    }
    pushdown(i);//向下传递
    if(tree[i*2].r>=l)
        add(i*2,l,r,k);
    if(tree[i*2+1].l<=r)
        add(i*2+1,l,r,k);
    tree[i].sum=tree[i*2].sum+tree[i*2+1].sum;
    return ;
}



long long cha(int i,int l,int r)
{
    if(tree[i].l>=l && tree[i].r<=r)
        return tree[i].sum;
    if(tree[i].r<l || tree[i].l>r)  
	return 0;
    pushdown(i);
    long long s=0;
    if(tree[i*2].r>=l)  
	s+=cha(i*2,l,r);
    if(tree[i*2+1].l<=r)  
	s+=cha(i*2+1,l,r);
    return s;
}

int main()
{
	cin>>n>>m;
	for(int i=1;i<=n;i++)
	{
		cin>>a[i];
	}
	build(1,1,n);
	while(m--)
	{
		cin>>flag;
		if(flag=='C')
		{
			long long x,y,z;
			cin>>x>>y>>z;
			add(1,x,y,z);
		}
		else
		{
			ans=0;
			long long x,y;
			cin>>x>>y;
			ans=cha(1,x,y);
			printf("%lld\n",ans);
		}
	}
	return 0;
}

 

 

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如若转载，请注明出处：/a/515726.html

如若内容造成侵权/违法违规/事实不符，请联系我们进行投诉反馈qq邮箱809451989@qq.com，一经查实，立即删除！

相关文章

前端返回 List＜Map＜String, Object＞＞中的vaue值里面包含一个Bigdecimal类型,序列化时小数点丢失，如何解决？

前端返回 List＜Map＜String, Object＞＞中的vaue值里面包含一个Bigdecimal类型,序列化时小数点丢失，如何解决？

&#x1f3c6;本文收录于「Bug调优」专栏&#xff0c;主要记录项目实战过程中的Bug之前因后果及提供真实有效的解决方案&#xff0c;希望能够助你一臂之力&#xff0c;帮你早日登顶实现财富自由&#x1f680;&#xff1b;同时&#xff0c;欢迎大家关注&&收藏&&…
阅读更多...
Windows 11安装kb5035853补丁时，提示错误0x800f0922，并且弹出“某些操作未按计划进行，不必担心，正在撤消更改。请不要关机”

Windows 11安装kb5035853补丁时，提示错误0x800f0922，并且弹出“某些操作未按计划进行，不必担心，正在撤消更改。请不要关机”

Windows 11安装kb5035853补丁时&#xff0c;提示错误0x800f0922&#xff0c;并且还在重启后弹出“某些操作未按计划进行&#xff0c;不必担心&#xff0c;正在撤消更改。请不要关机”&#xff0c;按微软官方的作法是&#xff1a;https://learn.microsoft.com/zh-cn/windows/rel…
阅读更多...
基于SpringBoot和Vue的音乐在线交流网站的设计和实现【附源码】

基于SpringBoot和Vue的音乐在线交流网站的设计和实现【附源码】

1、系统演示视频&#xff08;演示视频&#xff09; 2、需要交流和学习请联系
阅读更多...
【PLC一体机】GX Works2编程控制步进电机正反转

【PLC一体机】GX Works2编程控制步进电机正反转

今天博主和大家分享一下在GX Works2 中对PLC一体机编程&#xff0c;实现步进电机自动正反转的程序。 程序如下&#xff1a; 该程序有几个重要的地方和大家分享一下&#xff1a; 1、程序以中间寄存器M4开头。 博主想通过PLC一体机上的触摸屏控制程序是否运行&#xff0c;因此…
阅读更多...
多类别分类器（Machine Learning研习十八）

多类别分类器（Machine Learning研习十八）

多类别分类器 二元分类器可以区分两个类别&#xff0c;而多类别分类器&#xff08;也称为多叉分类器&#xff09;可以区分两个以上的类别。 一些 Scikit-Learn 分类器&#xff08;如 LogisticRegression、RandomForestClassifier 和 GaussianNB&#xff09;能够原生处理多个类…
阅读更多...
各类系统业务功能架构图整理

各类系统业务功能架构图整理

一、前言 很多软件系统一直经久不衰&#xff0c;主要这些系统都是一些生产工作经营不可或缺的系统。比如财务系统&#xff0c;商城系统&#xff0c;支付系统&#xff0c;供应链系统&#xff0c;人力资源管理系统&#xff0c;ERP系统等等。这些系统不管大公司还是小公司往往都需…
阅读更多...
VSCode美化

VSCode美化

今天有空收拾了一下VSCode&#xff0c;页面如下&#xff0c;个人觉得还是挺好看的~~ 1. 主题 Noctis 色彩较多&#xff0c;有种繁杂美。 我使用的是浅色主题的一款Noctis Hibernus 2. 字体 Maple Mono 官网&#xff1a;Maple-Font 我只安装了下图两个字体&#xff0c;使…
阅读更多...
jvm总结学习

jvm总结学习

四种加载器 1.启动类加载器 2.拓展类加载器 3.应用程序加载器 4.自定义加载器 沙箱机制 就是为了保证安全&#xff0c;增加的一些权限。 native方法区&#xff08;静态变量&#xff0c;常量&#xff0c;类信息&#xff08;构造方法&#xff0c;接口定义&#xff09;&…
阅读更多...
Python 代码混淆工具概述

Python 代码混淆工具概述

在保护Python代码安全方面&#xff0c;有多种混淆工具可供选择&#xff0c;包括 Cython, Nuitka, Pyminifier 和 IPA guard。本文将介绍这些工具的特点和适用情况&#xff0c;以及在实际应用中的注意事项。 &#x1f4dd; 摘要 本文探讨了几种常见的 Python 代码混淆工具&am…
阅读更多...
阿里云可观测 2024 年 3 月产品动态

阿里云可观测 2024 年 3 月产品动态

本月可观测热文回顾 文章一览&#xff1a; 全新架构&#xff01;日志服务 SLS 自研免登录方案发布 AIOps 智能运维&#xff1a;有没有比专家经验更优雅的错/慢调用分析工具&#xff1f; 一文看懂如何做好 SQL 质量监控 使用 SPL 高效实现 Flink SLS Connector 下推 功能快…
阅读更多...
HbnnMall电子商城系统介绍（功能与技术栈）

HbnnMall电子商城系统介绍（功能与技术栈）

今天在看我个人网站上的文章时&#xff0c;看到了曾经在2020年自己开发的电商系统。那时我已经入职小米有一段时间了&#xff0c;基本已经对各个业务线&#xff0c;各种业务知识有了系统性的了解和学习&#xff0c;所以想自己动手写一个电商系统&#xff0c;以便进一步提高自己…
阅读更多...
LeetCode刷题实战1：两数之和

LeetCode刷题实战1：两数之和

从今天开始加入刷题大军&#xff0c;把算法题刷爆&#xff0c;我们直接进入主题。 题目内容 给定一个整数数组 nums 和一个整数目标值 target&#xff0c;请你在该数组中找出 和为目标值 target 的那 两个 整数&#xff0c;并返回它们的数组下标。 你可以假设每种输入只会对应…
阅读更多...
经济学 生产成本 垄断

经济学 生产成本 垄断

经济利润&#xff1a;收益-显性成本-隐性成本 会计利润&#xff1a;收益-显性成本 隐性成本&#xff1a;间接的机会成本 成本分为两种&#xff1a;可变成本和固定成本 可变成本&#xff1a;随着生产产品数量发生改变 固定成本 平均成本&#xff1a;每一单单位产品的成本 通…
阅读更多...
二维码的生成、下载Java，并返回给前端展示

二维码的生成、下载Java，并返回给前端展示

分析 将生成的二维码图片&#xff0c;以IO流的方式&#xff0c;通过response响应体直接返回给请求方。 第一、不需要落到我们的磁盘&#xff0c;操作在内存中完成&#xff0c;效率比较高。 第二、所有生成二维码的请求&#xff0c;都可以访问这里&#xff0c;前端直接拿img标…
阅读更多...
vue想要突破全局样式限制又不影响别的页面样式怎么办

vue想要突破全局样式限制又不影响别的页面样式怎么办

<!-- 用scope盖不住全局&#xff0c;随意来个class匹配私定&#xff0c;搜索关键词&#xff1a;不要随便改&#xff0c;乱打class名 --> <style> .lkajsdfjkalsfhkljashkflhaskl .el-input.el-input--default.el-input--suffix { width: 160px !important; } …
阅读更多...
MySQL索引原理

MySQL索引原理

MySQL索引原理 1、Innodb中的B树是怎么产生的呢? 背景1.1、mysql索引使用B树&#xff0c;为什么&#xff1f;1.2、主键索引图示1.3、mysql最好使用自增ID&#xff1a;为什么呢&#xff1f;1.4、高度为3的B树能存多少条数据&#xff1f;a、假设2层b、假设3层 2、索引采用什么数…
阅读更多...
从0到1构建uniapp应用-store状态管理

从0到1构建uniapp应用-store状态管理

背景 在 UniApp的开发中&#xff0c;状态管理的目标是确保应用数据的一致性&#xff0c;提升用户体验&#xff0c;并简化开发者的工作流程。通过合理的状态管理&#xff0c;可以有效地处理用户交互、数据同步和界面更新等问题。 此文主要用store来管理用户的登陆信息。 重要…
阅读更多...
python--面向对象编程和类的定义，对象的创建

python--面向对象编程和类的定义，对象的创建

一、面向对象简介 1、什么是面向对象 面向对象是一种编程思想&#xff0c;把数据和对数据的多个操作方法封装在一起组成类&#xff0c;这样通过这个类创建出来的对象,就可以直接调用这些方法了。 2、面向对象相关的术语 类&#xff1a;用来描述具有相同的属性和方法的对象的…
阅读更多...
基于深度学习的花卉检测与识别系统（网页版+YOLOv8/v7/v6/v5代码+训练数据集）

基于深度学习的花卉检测与识别系统（网页版+YOLOv8/v7/v6/v5代码+训练数据集）

摘要&#xff1a;在本篇博客中&#xff0c;我们深入探讨了基于YOLOv8/v7/v6/v5的花卉检测与识别系统。核心上&#xff0c;我们采用了最新的YOLOv8技术&#xff0c;并整合了YOLOv7、YOLOv6、YOLOv5等先进算法&#xff0c;进行了细致的性能指标对比分析。我们详细介绍了当前国内外…
阅读更多...
刚刚，Sora官方发布首支MV

刚刚，Sora官方发布首支MV

ChatGPT狂飙160天&#xff0c;世界已经不是之前的样子。 新建了免费的人工智能中文站https://ai.weoknow.com 新建了收费的人工智能中文站ai人工智能工具 更多资源欢迎关注 AIGC&#xff0c;算是狠狠地震荡了一把音乐圈。 就在刚刚&#xff0c;OpenAI官方账号发布的一支由Sor…
阅读更多...
最新文章

Copyright @ 2022~2023