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

权值线段树 学习笔记

时间:2023-09-29 11:11:21浏览次数:36  
标签:return int 线段 tr mid 笔记 权值

8月集训学了权值线段树,当时没怎么加强训练。

国庆刚好开始有时间,巩固巩固。补上学习笔记。

首先介绍权值树。其本质是一个记录每个数出现次数的线段树,也就是由桶建成的树。

接下来介绍各种操作。

1.插入。

由于统计的是出现次数,从这个数往上依次加1即可。

void insert(int x,int l,int r,int k){
    //插入一个数k
    if(l==r){
        tr[x]++;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) insert(x*2,l,mid,k);
    else insert(x*2+1,mid+1,r,k);
    pushup(x);
}

2.删除。

同上,依次往上减-1。

void del(int x,int l,int r,int k){
    //删除一个数k
    if(l==r){
        tr[x]--;
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) del(x*2,l,mid,k);
    else del(x*2+1,mid+1,r,k);
    pushup(x);
}

3.查询区间数的数量。同线段树的查询。

int query(int x,int l,int r,int ql,int qr){
    //查询ql,qr之间一共有多少个数
    if(l>=ql&&r<=qr) return tr[x];
    int mid=(l+r)/2,sum=0;
    if(ql<=mid) sum=query(x*2,l,mid,ql,qr);
    if(qr>mid) sum+=query(x*2+1,mid+1,r,ql,qr);
    return sum;
}

4.查询第K大。(单纯的权值线段树只能查询整个区间。区间第K大需要树套树)

int kth(int x,int l,int r,int k){
    if(l==r) return l;//查到了,返回即可
    int mid=(l+r)/2;
    if(k<=tr[x*2]) return kth(x*2,l,mid,k); 
    return kth(x*2+1,mid+1,r,k-tr[x*2]);
}

5.查询排名。往下递归查找,每次加上左子树的值(因为左子树都比这个数要小)

int rnk(int x,int l,int r,int k){
    if(l==r) return 1;
    int mid=(l+r)/2;
    if(k<=mid) return rnk(x*2,l,mid,k);
    return rnk(x*2+1,mid+1,r,k)+tr[x*2];
}

6.前驱后继

前驱实际上就是比n的排名小一位的数,也就是kth(rnk(x)-1)

后继就是n+1的排名位置的数,也就是kth(rnk(x+1))

 7.空间优化。

离散化,动态开点。

咕咕咕

 

 

 

例题。

1. P3369 【模板】普通平衡树

使用了动态开点。

//produced by miya555
//stupid mistakes: query貌似一直出问题
//ideas: 尝试用权值线段树实现平衡树,先试试。
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ls (o<<1)
#define rs (ls|1)
const int N=500000;

int b[N],a[N],val[N],st[N],n,tot;
void add(int o,int l,int r,int k,int pos)
{
    st[o]+=pos;
    if(l==r) return;
    int mid=(l+r)>>1;
    if(k<=mid) add(ls,l,mid,k,pos);
    else add(rs,mid+1,r,k,pos);
}

int query(int o,int l,int r,int k)
{
    if(l==r) return 1;
    int mid=(l+r)>>1;
    if(k<=mid) return query(ls,l,mid,k);
    else return st[ls]+query(rs,mid+1,r,k);
}

int find(int o,int l,int r,int k)
{
    if(l==r) return l;
    int mid=(l+r)>>1;
    if(st[ls]>=k) return find(ls,l,mid,k);
    else return find(rs,mid+1,r,k-st[ls]);
}

main()
{
    cin>>n;
    for(int i=1;i<=n;i++)
    {
        cin>>val[i];
        cin>>a[i];
        if(val[i]!=4)
            b[++tot]=a[i];
    }
    
    sort(b+1,b+tot+1);
    
    for(int i=1;i<=n;i++)
    {
        if(val[i]!=4)
            a[i]=lower_bound(b+1,b+tot+1,a[i])-b;
    }
    for(int i=1;i<=n;i++)
    {
        
        int op=val[i];
         if(op==1){
             add(1,1,tot,a[i],1);
             
         }else if(op==2) {
             add(1,1,tot,a[i],-1);
             
             
         }else if(op==3) {
             cout<<query(1,1,tot,a[i])<<endl;
             
             
         }else if(op==4) {
             cout<<b[find(1,1,tot,a[i])]<<endl;
             
             
         }else if(op==5) {
             cout<<b[find(1,1,tot,query(1,1,tot,a[i])-1)]<<endl;
             
         }else{
             cout<<b[find(1,1,tot,query(1,1,tot,a[i]+1))]<<endl;
         }
        
    }
    return 0;
}

 

2.  P2073  送花

//produced by miya555
//stupid mistakes:
//ideas:搓一搓权值线段树板子
#include <bits/stdc++.h>
using namespace std;
const int N=1e7+10;
struct{
    int c,w;
} tr[8*N];
inline void pushup(int x){
    tr[x].c=tr[x*2].c+tr[x*2+1].c;
    tr[x].w=tr[x*2].w+tr[x*2+1].w;
}
void insert(int x,int l,int r,int k,int p){

    if(l==r){
        if(tr[x].c==0){
            tr[x].c+=p;
            
        }
        return;
    }
    int mid=(l+r)/2;
    if(k<=mid) insert(x*2,l,mid,k,p);
    else insert(x*2+1,mid+1,r,k,p);
    pushup(x);
}
void update(int u,int l,int r,int x,int v)    
{
    if(l==r)
    {
        if(tr[u].c==x) return;        
        tr[u].c=x;                    
        tr[u].w=v;
    }
    else
    {
        int mid=l+r>>1;        
        if(x<=mid) update(u<<1,l,mid,x,v);
        else update(u<<1|1,mid+1,r,x,v);
        pushup(u);
    }
}
void remove(int u,int l,int r,int s)    
{
    if(l==r) tr[u]={0,0};            
    else
    {
        int mid=l+r>>1;
        if(s)                            
        {
            if(!tr[u<<1|1].c) remove(u<<1,l,mid,s);    
            else remove(u<<1|1,mid+1,r,s);            
        }
        else                            
        {
            if(!tr[u<<1].c) remove(u<<1|1,mid+1,r,s);    
            else remove(u<<1,l,mid,s);
        }
        pushup(u);                        
    }
}
int kth(int x,int l,int r,int k){
    if(l==r) return l;
    int mid=(l+r)/2;
    if(k<=tr[x*2].c) return kth(x*2,l,mid,k); 
    return kth(x*2+1,mid+1,r,k-tr[x*2].c);
}

int n,y;
int t;
int main(){
    while(1){
        int opt,x;
        cin>>opt;
        if(opt==-1) break;
        if(opt==1){
            cin>>x>>y;
            update(1,1,1e6,y,x);
            t++;
        }
        else if(tr[1].c==0) continue;
        else if(opt==2) remove(1,1,1e6,1);
        else remove(1,1,1e6,0);
    }
    printf("%d %d\n",tr[1].w,tr[1].c);
}

 

 

 

 

标签:return,int,线段,tr,mid,笔记,权值
From: https://www.cnblogs.com/Miya555/p/17736861.html

相关文章

  • 矩阵学习笔记
    矩阵是一种数学概念,在\(OI\)中有着重要应用。一个矩阵有行,列,以及里面的数字。如图便是一个\(2\)行\(3\)列的矩阵:\[\begin{bmatrix}1&2&3\\4&5&6\\\end{bmatrix}\]矩阵数乘:\(\lambdaA\)就是将\(\lambda\)依次乘进每个矩阵。矩阵乘法:\(A\timesB=C\),那么\(C_{......
  • Unix/Linux系统编程学习笔记第七、八章
    Unix/Linux系统编程学习笔记第七、八章知识点归纳以及最有收获的内容文件操作级别文件和目录的基本操作创建文件:使用touch命令或编程语言中的文件创建函数。-创建目录:使用mkdir命令或编程语言中的目录创建函数。复制文件或目录:使用cp命令或编程语言中的复制函数。移......
  • 济南 CSP-S NOIP 储备营笔记
    Day1上午——基础算法模拟+枚举小前言碰到题目不会做->先写个模拟压压惊()枚举法枚举的思想是不断地猜测,从所有可能的集合中一一尝试,然后再判断是否符合题目的条件。单独提到枚举时我们往往认为这是一个暴力做法,但事实上并非如此,恰当的枚举往往会是解题的关键步骤。......
  • 读高性能MySQL(第4版)笔记17_复制(下)
    1. 复制切换1.1. 复制是高可用性的基础1.1.1. 总是保留一份持续更新的副本数据,会让灾难恢复更简单1.2. “切换副本”(promotingareplica)和“故障切换”(failingover)是同义词1.2.1. 意味着源服务器不再接收写入,并将副本提升为新的源服务器1.3. 计划内切换1.3.1. 常......
  • 学习笔记4
    第7章文件操作——教材知识点归纳7.1文件操作级别在Linux中,文件操作可以分为五个级别,从最底层到最高层分别如下:硬件级别:这一级别包括诸如fdisk(用于分区)、mkfs(用于格式化磁盘分区)、fsck(用于检查系统)以及碎片整理(用于压缩文件系统中的文件)等操作。内核级别的文件系统函......
  • Linux第7、8章学习笔记
    第七、八章学习笔记第七章文件操作文件操作级别文件操作分为五个级别,按照从高到低的顺序如下:(1)硬件级别:硬件级别的文件操作包括:fdisk:将硬盘、U盘或SDC盘分区。mkfs:格式化磁盘分区、为系统做好准备。fsck:检查和维修系统。碎片整理:压缩文件系统中的文件。大多数是......
  • 《软件工程:一种实践方法》读书笔记二
    读完本书后,我深刻认识到了软件工程的重要性。软件工程不仅仅是一套流程和工具,更是一种系统的思维方式和态度。通过本书所提供的实践方法,我们可以更好地进行软件开发和维护,提高软件质量,降低维护成本。同时,本书也让我明白了软件工程师的责任感和使命感。作为软件工程师,我们需要时刻......
  • Linux第七、八章学习笔记
    第七、八章学习笔记第七章文件操作文件操作级别文件操作分为五个级别,按照从高到低的顺序如下:(1)硬件级别:硬件级别的文件操作包括:fdisk:将硬盘、U盘或SDC盘分区。mkfs:格式化磁盘分区、为系统做好准备。fsck:检查和维修系统。碎片整理:压缩文件系统中的文件。大多数是......
  • 学习笔记4 第七八章的自学归纳
    第7章文件操作文件操作五个级别1.硬件级别:普通用户不会接触,但它是创建和维护系统不可缺少的工具fdisk、mkfs、fsck2.操作系统内核中的文件系统函数每个操作系统内核均可为基本文件操作提供支持。在类unix函数中前缀k表示内核函数3.系统调用用户模式程序使用系统调用来访问......
  • 信息安全系统设计与实现——学习笔记4
    任务详情:自学教材第7,8章,提交学习笔记(10分)Part1知识点归纳&GPT提问知识点归纳chap7文件操作级别硬件级别fdiskmkfsfsck碎片整理操作系统内核中的文件系统函数系统调用I/O库函数用户命令sh脚本文件I/O操作低级别文件操作分区Command(mforhelp):m---......