线段树(线段树入门笔记)

简介: 线段树(线段树入门笔记)

什么是线段树
线段树是一种二叉搜索树,它将一个区间划分成一些单元区间,每个单元区间对应线段树中的一个叶结点。
对于线段树中的每一个非叶节点[a,b],它的左儿子表示的区间为[a,(a+b)/2],右儿子表示的区间为[(a+b)/2+1,b]。因此线段树是平衡二叉树,最后的子节点数目为N,即整个线段区间的长度。
在这里插入图片描述
定义结点
一般定义成结构体类型,其成员可以根据需要增加

struct node{
   
   
    int l;//左区间端点 
    int r;//右区间端点 
    int val;//此节点存值 
    int len;//子结点管理区间长度 
}tree[1005];

建树

void build(int cur, int l, int r)
{
   
   
    int mid=(l+r)/2;
    tree[cur].l=l, tree[cur].r=r;
    tree[cur].val=0, tree[cur].len=r-l+1;
    if (l==r)//只有到达叶结点时才把数组的值赋给它 
        tree[cur].val=arr[l];//arr为输入数据的数组
    else{
   
   
        build(cur*2, l, mid);
        build(cur*2+1, mid+1, r);
        tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;//回溯过程中更新父结点 
    }
}

单点更新

void updata(int cur, int id, int val)//cur为节点编号,id为修改数据的编号,val为增加的值 
{
   
   
    int l=tree[cur].l, r=tree[cur].r;
    int mid=(l+r)/2;
    if (l==r){
   
   
        tree[cur].val+=val;
        return;
    }
    if (id<=mid)
        updata(cur*2, id, val);
    else
        updata(cur*2+1, id, val);
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;//回溯过程中更新父结点 
}

区间查询

int query(int cur, int ql, int qr)
{
   
   
    int l=tree[cur].l, r=tree[cur].r;
    int mid=(l+r)/2, res=0;
    if (ql<=l && r<=qr)//如果此节点的区间在查询区间内,直接返回 
        return tree[cur].val;
    if (ql<=mid)
        res+=query(cur*2, ql, qr);
    if (qr>mid)//注意这里是两个if,不是分支关系 
        res+=query(cur*2+1, ql, qr);
    return res;
}

完整模板

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;

struct node{
   
   
    int l;
    int r;
    int val;
    int len;
    int lazy;
}tree [505];
int arr[505];

void pushup(int cur){
   
   
    tree[cur].val=tree[cur*2].val+tree[cur*2+1].val;
}

void pushdown(int cur){
   
   
    if (tree[cur].lazy!=0){
   
   
        tree[cur*2].lazy+=tree[cur].lazy;
        tree[cur*2+1].lazy+=tree[cur].lazy;
        tree[cur*2].val+=tree[cur*2].len*tree[cur].lazy;
        tree[cur*2+1].val+=tree[cur*2+1].len*tree[cur].lazy;
        tree[cur].lazy=0;
    }
}
//建树 
void build(int cur, int l, int r){
   
   
    int mid=(l+r)/2;
    tree[cur].l=l, tree[cur].r=r;
    tree[cur].val=0, tree[cur].len=r-l+1;
    tree[cur].lazy=0;
    if (l==r)
        tree[cur].val=arr[l];
    else{
   
   
        build(cur*2, l, mid);
        build(cur*2+1, mid+1, r);
        pushup(cur);
    }
}

//单点更新  加值 
void update_point(int cur, int pos, int val)//cur为节点编号,id为修改数据的编号,val为增加的值 
{
   
   
    int l=tree[cur].l, r=tree[cur].r;
    int mid=(l+r)/2;
    if (l==r){
   
   
        tree[cur].val+=val;
        tree[cur].lazy+=val;
        return;
    }
    if (pos<=mid)
        update_point(cur*2, pos, val);
    else
        update_point(cur*2+1, pos, val);
    pushup(cur);
} 
//单点查询
int query_point(int cur, int pos){
   
   
    if (tree[cur].l==tree[cur].r)
        return tree[cur].val;
    pushdown(cur);

    int mid=(tree[cur].l+tree[cur].r)/2;
    if (pos<mid)
        query_point(cur*2, pos);
    else
        query_point(cur*2+1, pos);
} 
//区间查询
int query_interval(int cur, int ql, int qr){
   
   
    if (ql<=tree[cur].l && tree[cur].r<=qr)
        return tree[cur].val;
    pushdown(cur);

    int ans=0;
    int mid=(tree[cur].l+tree[cur].r)/2;
    if (ql<=mid)
        ans+=query_interval(cur*2, ql, qr);
    if (qr>mid)
        ans+=query_interval(cur*2+1, ql, qr);
    return ans; 
} 
//区间更新 加值 
void update_interval(int cur, int l, int r, int val){
   
   
    if (l<=tree[cur].l && tree[cur].r<=r){
   
   
        tree[cur].val+=(tree[cur].r-tree[cur].l+1)*val;
        tree[cur].lazy+=val;
        return;
    }
    pushdown(cur);

    int mid=(tree[cur].l+tree[cur].r)/2;
    if (l<=mid)
        update_interval(cur*2, l, r, val);
    if (r>mid)
        update_interval(cur*2+1, l, r, val);

    pushup(cur);
} 
int main(){
   
   

    return 0;
}

参考链接:
https://blog.csdn.net/zhhe0101/article/details/53871453
https://blog.csdn.net/weixin_40788897/article/details/81539106

相关文章
|
安全 Java
安装burp2022 --illegal-access=permit
安装burp2022 --illegal-access=permit
211 0
|
7月前
|
JSON Java Nacos
SpringCloud 应用 Nacos 配置中心注解
在 Spring Cloud 应用中可以非常低成本地集成 Nacos 实现配置动态刷新,在应用程序代码中通过 Spring 官方的注解 @Value 和 @ConfigurationProperties,引用 Spring enviroment 上下文中的属性值,这种用法的最大优点是无代码层面侵入性,但也存在诸多限制,为了解决问题,提升应用接入 Nacos 配置中心的易用性,Spring Cloud Alibaba 发布一套全新的 Nacos 配置中心的注解。
694 112
|
8月前
|
数据采集 人工智能 弹性计算
从零到英雄:利用百炼平台打造高效情感分析智能体的全攻略
百炼平台是阿里巴巴推出的面向开发者的AI模型训练和推理平台,提供丰富工具和服务,支持从需求分析到部署上线的全流程。本文以构建情感分析系统为例,详细介绍如何利用百炼平台完成数据准备、模型选择与训练、评估调优及最终部署。
490 1
|
8月前
|
搜索推荐 关系型数据库 MySQL
mysql like查询优化
通过合理的索引设计、使用全文索引、优化查询结构以及考虑分片和分区表,可以显著提高MySQL中 `LIKE`查询的性能。针对不同的应用场景选择合适的优化策略,能够有效地提升数据库查询效率,减少查询时间。希望这些方法和技巧能帮助您优化MySQL数据库中的模糊查询。
894 4
|
JSON JavaScript 数据安全/隐私保护
npm命令:常用npm命令及其详解!
npm命令:常用npm命令及其详解!
|
运维 数据中心
计算巢资源组功能的最佳实践
计算巢简介计算巢是阿里云开放给ISV与其客户的服务管理PaaS平台,旨在解决ISV云上交付、部署、运维问题,建立ISV与客户之间的通道。针对ISV的实际场景,计算巢提供了私有化部署、托管版部署、代运维服务三种模式。托管版和私有化部署的区别是针对于部署在ISV的账号下还是部署在用户账号下。本文主要介绍计算巢不同场景下使用资源组功能的最佳实践。功能介绍资源组能够对用户拥有的云资源从用途、权限、归属等维
计算巢资源组功能的最佳实践
|
Java 微服务 Spring
Spring Cloud Alibaba - 15 微服务之间使用Feign实现参数的透传
Spring Cloud Alibaba - 15 微服务之间使用Feign实现参数的透传
276 0
|
Web App开发 前端开发 JavaScript
Web前端快速开发 Bootstrap 响应式UI框架
Web前端快速开发 Bootstrap 响应式UI框架
726 0
Web前端快速开发 Bootstrap 响应式UI框架
88.合并两个有序数组(LeetCode)
88.合并两个有序数组(LeetCode)
|
人工智能 并行计算 计算机视觉