首页 > 其他分享 >基本线段树以及相关例题

基本线段树以及相关例题

时间：2024-04-04 17:29:06浏览次数：26  
标签：int 线段 tree mid long 相关 例题 lz sum

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;
}

 

 

标签：int,线段,tree,mid,long,相关,例题,lz,sum
From： https://blog.csdn.net/2301_80475191/article/details/137376013

相关文章

  • Java：多线程相关知识概念
    Java中的多线程是指在单个程序中并行执行多个线程（即执行路径或任务）的能力。多线程在Java中是一个核心概念，它允许应用程序更有效地利用CPU资源，同时还能进行并发操作。以下是Java中多线程相关的详细知识：线程的基本概念线程（Thread）:是操作系统能够进行运算调度的最小单位。它......
  • 【递推与递归】python例题详解
    文章目录1、递归实现指数型枚举2、递归实现排列型枚举3、递归实现组合型枚举4、简单斐波那契5、带分数6、翻硬币1、递归实现指数型枚举题目从 1∼n这 n个整数中随机选取任意多个，输出所有可能的选择方案。输入格式输入一个整数 n。输出格式每行输出一种方案。同一......
  • pm2 相关命令
    安装npminstallpm2-g#全局安装pm2先关命令pm2startapp.js-i4#后台运行pm2，启动4个app.js#也可以把'max'参数传递给start#正确的进程数目依赖于Cpu的核心数目pm2startapp.js--namemy-api#命名进程......
  • |行业洞察·AIGC|《AIGC行业深度：发展情况、商业模式、产业链及相关公司深度梳理》
    报告主要内容的解读：1.行业概述概念：AIGC是一种内容生产方式，通过深度学习技术，输入数据后由AI生成内容。它代表了从PGC（ProfessionallyGeneratedContent）和UGC（UserGeneratedContent）到AIUGC的演变。AI与AIGC的演进历程：AI的发展经历了从决策式AI到生成式AI的过程。生成式AI......
  • 【数据处理包Pandas】分组及相关操作
    目录一、初步认识分组并查看分组信息（一）通过聚合函数查看分组信息（二）转换成列表查看所有组的信息（三）通过循环查看各组的名称和组中的数据信息（四）通过get_group()方法直接获得一组数据二、分组再认识三、分组的执行过程（一）split阶段：创建分组的常见形式（二）应用阶段：对数据进行必......
  • [算法学习笔记] 线段树
    前言线段树可以维护一系列区间问题。包括但不限于区间加，区间乘，区间最值等。本文主要介绍最基础的区间修改区间查询。你可以认为是模板线段树的解析。本文将持续更新。例题给定一个数列，需要支持如下两种操作：\(1\)\(x\)\(y\)\(k\)将区间\([x,y]\)中每一个数加\(k\)......
  • 自动驾驶涉及相关的技术
    当科幻走进现实，当影视照进生活，无数次憧憬的自动驾驶，正在慢慢的梦想成真。小时候天马星空的想象，现在正悄无声息的改变着我们的生活。随着汽车电动化进程的加快，自动驾驶技术映入眼帘，很多人可能感觉遥不可及，其实你每天都开的汽车上，或多或少已经增加了部分自动驾驶的功能。那么咱就......
  • 数据结构——线段树
    本来是想先写树状数组的，但想到要在树状数组里面用到这篇文章，就先写这个了。线段树的思想线段树是在用一颗树存一个数组中的所有数以及他们所有的2的次方数长度的区间，具体样子如下：                      [1~8]     ......
  • asyncio 异步io相关知识
    importasyncio#运行器asyncdefhello_async(delay,words):awaitasyncio.sleep(delay)print(words)#协程与任务asyncdeftest_async():#等待第一个协程hello_async执行完以后再串行执行下一个任务，两个协程没有并发效果start_time=time.time()prin......
  • 在 PowerShell 中，您可以使用以下命令来管理 DNS 相关的任务以及 DNS 缓存
    在PowerShell中，您可以使用以下命令来管理DNS相关的任务以及DNS缓存：获取当前计算机的DNS客户端配置信息powershellCopyCodeGet-DnsClientGet-DnsClientInterfaceAlias       InterfaceConnectionSpecificSuffixConnectionSpecificSuffixRegi......

赞助商

阅读排行

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

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

Copyright © 2020-2023 IPS99 版权所有 IPS99