首页 > 其他分享 >线段树 学习笔记

线段树 学习笔记

时间:2024-03-11 11:23:20浏览次数:32  
标签:return int res 线段 笔记 学习 const ll

简介

略。

-1 一个模板

改编自 tourist。其中只需要写 apply、pushdown、merge

class segtree {
public:
    struct node {
        // don't forget to set default value (used for leaves)
        // not necessarily neutral element!
        int sum=0,add=0;
        void apply(int l,int r,int v) {
            sum+=(r-l+1)*v,add+=v;
        }
    };

    node merge(const node &a,const node &b) const {
        node res;
        res.sum=a.sum+b.sum;
        return res;
    }

    inline void pushdown(int x,int l,int r) {
        int y=(l+r)>>1;
        int z=x+((y-l+1)<<1);
        // pushdown from x into (x + 1) and z
        if(tree[x].add!=0) {
            tree[x+1].apply(l,y,tree[x].add);
            tree[z].apply(y+1,r,tree[x].add);
            tree[x].add=0;
        }
    }

    inline void pushup(int x,int z) {
        tree[x]=merge(tree[x+1],tree[z]);
    }

    int n;
    vector<node> tree;

    void build(int x,int l,int r) {
        if(l==r) {
            return;
        }
        int y=(l+r)>>1,z=x+((y-l+1)<<1);
        build(x+1,l,y),build(z,y+1,r);
        pushup(x,z);
    }

    template <typename M>
    void build(int x,int l,int r,const vector<M> &v) {
        if(l==r) {
            tree[x].apply(l,r,v[l]);
            return;
        }
        int y=(l+r)>>1,z=x+((y-l+1)<<1);
        build(x+1,l,y,v),build(z,y+1,r,v);
        pushup(x,z);
    }

    node get(int x,int l,int r,int ll,int rr) {
        if(ll<=l&&r<=rr) {
            return tree[x];
        }
        int y=(l+r)>>1,z=x+((y-l+1)<<1);
        pushdown(x,l,r);
        node res{};
        if(rr<=y) res=get(x+1,l,y,ll,rr);
        else if(ll>y) res=get(z,y+1,r,ll,rr);
        else res=merge(get(x+1,l,y,ll,rr),get(z,y+1,r,ll,rr));
        pushup(x,z);
        return res;
    }

    template <typename... M>
    void modify(int x,int l,int r,int ll,int rr,const M&... v) {
        if(ll<=l&&r<=rr) {
            tree[x].apply(l,r,v...);
            return;
        }
        int y=(l+r)>>1,z=x+((y-l+1)<<1);
        pushdown(x,l,r);
        if(ll<=y) modify(x+1,l,y,ll,rr,v...);
        if(rr>y) modify(z,y+1,r,ll,rr,v...);
        pushup(x,z);
    }

    int find_first_knowingly(int x,int l,int r,const function<bool(const node&)> &f) {
        if(l==r) return l;
        pushdown(x,l,r);
        int y=(l+r)>>1,z=x+((y-l+1)<<1);
        int res;
        if(f(tree[x+1])) res=find_first_knowingly(x+1,l,y,f);
        else res=find_first_knowingly(z,y+1,r,f);
        pushup(x,z);
        return res;
    }

    int find_first(int x,int l,int r,int ll,int rr,const function<bool(const node&)> &f) {
        if(ll<=l&&r<=rr) {
            if(!f(tree[x])) return -1;
            return find_first_knowingly(x,l,r,f);
        }
        pushdown(x,l,r);
        int y=(l+r)>>1;
        int z=x+((y-l+1)<<1);
        int res=-1;
        if(ll<=y) res=find_first(x+1,l,y,ll,rr,f);
        if(rr>y&&res==-1) res=find_first(z,y+1,r,ll,rr,f);
        pushup(x,z);
        return res;
    }

    int find_last_knowingly(int x,int l,int r,const function<bool(const node&)> &f) {
        if(l==r) {
            return l;
        }
        pushdown(x,l,r);
        int y=(l+r)>>1,z=x+((y-l+1)<<1);
        int res;
        if(f(tree[z])) res=find_last_knowingly(z,y+1,r,f);
        else res=find_last_knowingly(x+1,l,y,f);
        pushup(x,z);
        return res;
    }

    int find_last(int x,int l,int r,int ll,int rr,const function<bool(const node&)> &f) {
        if(ll<=l&&r<=rr) {
            if(!f(tree[x])) return -1;
            return find_last_knowingly(x,l,r,f);
        }
        pushdown(x,l,r);
        int y=(l+r)>>1,z=x+((y-l+1)<<1);
        int res=-1;
        if(rr>y) res=find_last(z,y+1,r,ll,rr,f);
        if(ll<=y&&res==-1) res=find_last(x+1,l,y,ll,rr,f);
        pushup(x,z);
        return res;
    }

    segtree(int _n): n(_n) {
        assert(n>0);
        tree.resize(2*n-1);
        build(0,0,n-1);
    }

    template <typename M>
    segtree(const vector<M> &v) {
        n=v.size();
        assert(n>0);
        tree.resize(2*n-1);
        build(0,0,n-1,v);
    }

    node get(int ll,int rr) {
        assert(0<=ll&&ll<=rr&&rr<=n-1);
        return get(0,0,n-1,ll,rr);
    }

    node get(int p) {
        assert(0<=p&&p<=n-1);
        return get(0,0,n-1,p,p);
    }

    template <typename... M>
    void modify(int ll,int rr,const M&... v) {
        assert(0<=ll&&ll<=rr&&rr<=n-1);
        modify(0,0,n-1,ll,rr,v...);
    }

    // find_first and find_last call all FALSE elements
    // to the left (right) of the sought position exactly once

    int find_first(int ll,int rr,const function<bool(const node&)> &f) {
        assert(0<=ll&&ll<=rr&&rr<=n-1);
        return find_first(0,0,n-1,ll,rr,f);
    }

    int find_last(int ll,int rr,const function<bool(const node&)> &f) {
        assert(0<=ll&&ll<=rr&&rr<=n-1);
        return find_last(0,0,n-1,ll,rr,f);
    }
};

0. 一些简单的约定

令 ls 表示左儿子,rs 表示右儿子,mid 表示区间中点(即 \((l+r)/2\))

1. 一般线段树的常见优化技巧

1.1 动态开点线段树

对于普通的线段树节点 \(x\),定义其左儿子的编号为 \(2x\),右儿子的编号为 \(2x+1\)。

但是如果在长度为 \(1e9\) 的序列中做区间加区间求和,普通线段树无法高效地解决问题,因此产生动态开点线段树。

对于每个节点,维护其 ls 和 rs 的编号,修改下传时若对应儿子为空就新建一个节点,可以通过传递引用值方便地实现。查询时如果走到空节点就直接返回。

1.2 两倍空间线段树

令区间 \([l,r]\) 的编号为 \((l+r)\operatorname{or}[l\ne r]\)。

一个节点 \([x,l,r]\) 的左儿子编号为 \(mid\times 2\),右儿子编号为 \(mid \times 2+1\)。

容易证明这是两倍空间。

1.3 标记永久化

考虑每次不递归,直接打标记,这样省去了 pushdown 的常数,但是需要在 upd 和 query 时计算当前区间和查询区间的贡献。

2. 权值线段树

类似线段树维护一个桶,可以支持单点插入,区间查询 x 的排名,第 k 小(线段树二分)。

3. 线段树合并

考虑如果能快速合并叶子节点的信息和 pushup,就能合并快速合并两棵线段树。
动态开点,对空区间返回,否则合并叶子节点之后 pushup。

int merge(int l,int r,int x,int y) {
    if(!x||!y) return x|y;//or x^y.
    int z=++cnt;
    if(l==r) return /* 合并叶子 x 和 y */,z;
    ls[z]=merge(l,mid,ls[x],ls[y]);
    rs[z]=merge(mid+1,r,rs[x],rs[y]);
    return /*pushup*/,z;
}

参考资料:
1

2

标签:return,int,res,线段,笔记,学习,const,ll
From: https://www.cnblogs.com/lgh-blog/p/18061312

相关文章

  • 狂神说Java——Mybatis学习笔记
    前言:配合狂神老师的教学视频使用效果更佳:https://www.bilibili.com/video/BV1NE411Q7Nx/?spm_id_from=333.1007.top_right_bar_window_custom_collection.content.click&vd_source=4c3c519d33c113799489c7417a0a4c0e1、简介环境说明:jdk8+MySQL5.7.19maven-3.6.......
  • 学习Django【1】模型
    编辑models.py文件,改变模型。运行pythonmanage.pymakemigrations为模型的改变生成迁移文件。运行pythonmanage.pymigrate来应用数据库迁移。1、定义模型-也就是数据库结构设计和附加的其它元数据。大白话:数据库建表。2、使用命令pythonmanage.pym......
  • BGRL论文阅读笔记
    BGRL论文阅读笔记Abstract​ 自监督学习提供了一个有前途的途径来消除昂贵的标签信息的需要。然而,为了实现最先进的性能,方法通常需要大量的负的例子,并依赖于复杂的扩充。这可能会非常昂贵,特别是对于大型图形。为了解决这些挑战,我们引入了BootstrappedGraphLatent(BGRL)——一种......
  • Vue学习笔记42--ref
    Vue==>refref属性被用来给元素或子组件注册引用信息(id的替代者)应用在html标签上获取的是真实的DOM元素,应用在组件标签上是组件实例对象(vc)使用方式:声明标识:<h1ref="xxx">。。。。。。</h1>或<Schoolref="xxx"></School>——School为组件获取方式:this.$refs.xxx......
  • Amazon SageMaker 机器学习之旅的助推器
    授权声明:本篇文章授权活动官方亚马逊云科技文章转发、改写权,包括不限于在亚马逊云科技开发者社区,知乎,自媒体平台,第三方开发者媒体等亚马逊云科技官方渠道。一、前言在当今的数字化时代,人工智能和机器学习已经成为推动社会进步的重要引擎。亚马逊云科技在2023re:Invent全......
  • Augmentation-Free Self-Supervised Learning on Graphs论文阅读笔记
    Abstract我们认为,如果没有精心设计的增强技术,图上的扩充可能会任意的做出表现,因为图的底层语义会极大地变化。因此,现有的基于增强的方法的性能高度依赖于增强方案的选择,即与增强相关的超参数。在本文中,我们提出了一种新的无增强图自监督学习框架,即AFGRL。具体地说,我们发现通过与......
  • 线段树学习笔记(更新中)
    本文章开始写作于2024年3月10日22:48,这也是我第一次没有参考板子,独立写出一个线段树的时刻(虽然只是板子题并且debug的时候还是参考了一下)写这个主要是为了我自己以后复习起来方便,毕竟这玩意还是极其容易写挂的注意:以下内容中标为斜体的是需要按照题目要求具体情况具体分析的,文章......
  • Typescript学习笔记(一)
    学习日期:03-09-2024关键字:Typescript;安装;原始数据类型;Any类型;数组;元组;Typescript是Javascript的超集,显著区别是加了静态类型风格的类型系统、es6-es10-esnext的语法支持安装npminstall-gtypescript原始数据类型Boolean、Null、Undefined、Number、BigInt、String、Sy......
  • C#的笔记~TWO
    1、标识符命名的两个注意事项(1)标识符不能与C#关键字冲突(2)标识符区分大小写intage=30;intAge=30;【这两个符合规则】2、两种标识符命名方法:(1)Pascal命名法:所有单词第一个字母大写,其它字母小写。eg.UserGetinfo(2)Camel命名法:除了第一个单词,所有单词第一个字母......
  • 大型数据库应用——一些笔记
    这学期选了大型数据库应用,主要是和java一起用的,然后这里是一些笔记,可能会加上之前的一些笔记,之前学过数据库原理。一、介绍一些数据库1数据库分类数据库根据数据结构可分为关系型数据库和非关系型数据库。非关系型数据库中根据应用场景又可分为键......