首页 > 编程语言 >[Java]线段树

[Java]线段树

时间:2023-07-04 23:11:05浏览次数:183  
标签:Node Java min int 线段 tr mid sum

线段树

不含懒标记(单点修改)

image-20230704210835506

代码

维护区间最大/最小值

Node[] tr = new Node[400010];
class Node{
    int l, r, max, min;
    Node(int l, int r, int max, int min){
        this.l = l;
        this.r = r;
        this.max = max;
        this.min = min;
    }
}

void build(int u, int l, int r){
    tr[u] = new Node(l, r, 0, 0x3f3f3f3f);
    if(l == r) return ;
    int mid = l + r >> 1;
    build(u << 1, l, mid);
    build(u << 1 | 1, mid + 1, r);
}

void pushup(int u){
    tr[u].max = Math.max(tr[u << 1].max, tr[u << 1 | 1].max);
    tr[u].min = Math.min(tr[u << 1].min, tr[u << 1 | 1].min);
}

int query1(int u, int l, int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].max;
    int mid = tr[u].l + tr[u].r >> 1, v = 0;
    if(l <= mid) v = query1(u << 1, l, r);
    if(r > mid) v = Math.max(v, query1(u << 1 | 1, l, r));
    return v;
}

int query2(int u, int l, int r){
    if(l <= tr[u].l && tr[u].r <= r) return tr[u].min;
    int mid = tr[u].l + tr[u].r >> 1, v = 0x3f3f3f3f;
    if(l <= mid) v = query2(u << 1, l, r);
    if(r > mid) v = Math.min(v, query2(u << 1 | 1, l, r));
    return v;
}

void update(int u, int x, int v){
    if(tr[u].l == x && tr[u].r == x) {
        tr[u].max = v;
        tr[u].min = v;
    }
    else{
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) update(u << 1, x, v);
        else update(u << 1 | 1, x, v);
        pushup(u);
    }
}

含懒标记(区间修改)

image-20230704211105087

代码

static Node[] tr = new Node[4 * N];
static class Node {
    int l, r;
    long sum, add;

    public Node(int l, int r, long sum, long add) {
        this.l = l;
        this.r = r;
        this.sum = sum;
        this.add = add;
    }
}

static void pushup(int u){
    tr[u].sum = tr[u << 1].sum + tr[u << 1 | 1].sum;
}

static void pushdown(int u){
    Node root = tr[u], left = tr[u << 1], right = tr[u << 1 | 1];
    if(root.add != 0){
        left.add += root.add;
        left.sum += (left.r - left.l + 1) * root.add;
        right.add += root.add;
        right.sum += (right.r - right.l + 1) * root.add;
        root.add = 0;
    }
}

static void build(int u, int l, int r){
    if(l == r) tr[u] = new Node(l, r, w[l], 0);
    else{
        tr[u] = new Node(l, r, 0, 0);
        int mid = l + r >> 1;
        build(u << 1, l, mid);
        build(u << 1 | 1, mid + 1, r);
        pushup(u);
    }
}

static void modify(int u, int l, int r, int d){
    if(tr[u].l >= l && tr[u].r <= r) {
        tr[u].add += d;
        tr[u].sum += (long) (tr[u].r - tr[u].l + 1) * d;
    }else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if(l <= mid) modify(u << 1, l, r, d);
        if(r > mid) modify(u << 1 | 1, l, r, d);
        pushup(u);
    }
}

static long query(int u, int l, int r){
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum;
    else{
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        long res = 0;
        if(l <= mid) res = query(u << 1, l, r);
        if(r > mid) res += query(u << 1 | 1, l, r);
        return res;
    }
}

标签:Node,Java,min,int,线段,tr,mid,sum
From: https://www.cnblogs.com/tobuv/p/17527329.html

相关文章

  • 面试现场简单几道java算法题, 你能写出几道?
    这两天小编逛论坛的时候发现一个很有意思的事情,就是一位互联网公司的面试官分享的,他们最近想招一批java的实习生,所以他们的面试题并不难,但是前来面试的人,却很多都挂在了几道算法题上,要么就是逻辑不严谨,要么就是题目都看不懂的,还有就是书写错误的,这让他感到很诧异,毕竟算法其实对于......
  • Java源码系列4——HashMap扩容时究竟对链表和红黑树做了什么?
    Photobyhippopx.com我们知道HashMap的底层是由数组,链表,红黑树组成的,在HashMap做扩容操作时,除了把数组容量扩大为原来的两倍外,还会对所有元素重新计算hash值,因为长度扩大以后,hash值也随之改变。如果是简单的Node对象,只需要重新计算下标放进去就可以了,如果是链表和红黑......
  • Java17新特性及代码示例:还在使用Java8? 这5个Java17新功能,你会喜欢的
    SpringBoot3.0最低支持JDK17,各开源软件正在全面拥抱JDK17.有升级计划的调查受访者中,37%的人计划在未来六个月内升级到2021年9月份发布的LTS版本JDK17。另有25%的人计划在未来6到12个月内升级到JDK17。这5个你喜欢的JDK17新功能,会让你升级JDK17吗?1.record类(记录类)传统的......
  • Java9-17新特性解读+案例+说明+注意+发展趋势
    前言Java8出来这么多年后,已经成为企业最成熟稳定的版本,相信绝大部分公司用的还是这个版本,但是一眨眼今年Java19都出来了,相信很多Java工程师忙于学习工作对新特性没什么了解,有的话也仅限于某一块。本篇就是博主对自己感觉有用的新特性做了一个案例验证及简要说明,整合起来分享给......
  • 关于JAVA项目公共字段自动填充的理解
    公共字段字段填充是什么? “公共字段自动填充”顾名思义,其实就是省略了在程序当中对某些字段手动填写的步骤,大大提高了效率! 为什么要使用公共字段填充技术在我们的程序当中? 在我们项目的开发中,当我们在修改数据库中的某些值的时候,有一些字段属于公共子段,就是有些字段不仅是......
  • Spring Boot 3.0.0 来啦!最小依赖 Java17!升还是不升?
    Spring官方于2022年1月20日发布SpringBoot3.0.0-M1版本,预示开启了SpringBoot3.0的里程碑。官方公告下的中文评论有点东西。。。熟悉的味道!就是那个味!  分享一篇朋友对SpringBoot3.0的介绍:生还是不生?SpringBoot3版本有起飞前兆,最小依赖Java17!一直......
  • Java数组和数据存储
    数组的定义数组是相同类型数据的有序集合。其中,每一个数据称作一个元素,每个元素可以通过一个索引(下标)来访问它们。数组的四个基本特点:1.长度是确定的。数组一旦被创建,它的大小就是不可以改变的。2.其元素的类型必须是相同类型,不允许出现混合类型。3.数组类型可以是任何数据类......
  • 模拟双色球彩票系统(java)
    一、问题描述 注:六个红色球号码均不同,蓝色球号码可以红色球号码相同;二、设计思路(1)先随机出一个中奖号码,依据这个号码对后续进行颁奖;(2)再从用户端接收对应的6个红色球号码以及1个蓝色球号码;(3)将中奖号码与用户号码进行对比,得出对应的中奖结果;ps:”如何得到不重复的随机数“值......
  • GitHub上最热门的Java开源项目
    这是一个轻快,简洁,功能强大,使用Java开发的博客系统。2jeecg-boothttps://github.com/zhangdaiscott/jeecg-bootStar2873这是一款基于代码生成器的JAVA快速开发平台!提高UI能力的同时,降低前后分离的开发成本,JeecgBoot还独创在线开发模式,No代码概念,一系列在线智能开发:在线配置......
  • 高级Java开发面试常用题的答案
    一、数据结构与算法基础·说一下几种常见的排序算法和分别的复杂度。·用Java写一个冒泡排序算法/**现在有一个包含1000个数的数组,仅前面100个无序,后面900个都已排好序且都大于前面100个数字,那么在第一趟遍历后,最后发生交换的位置必定小于100,且这个位置之后的数据必定已......