首页 > 其他分享 >线段树

线段树

时间:2023-08-05 16:56:22浏览次数:35  
标签:lc int 线段 tr add rc sum

线段树

除了最后一层满二叉树,用堆(一维数组)来存树,一般来说,开4n的空间

线段树

build(int u, int l, int r)

将一段区间初始化为线段树

push up()

由子节点更新父节点的信息

push down()(懒标记)

把信息递归的更新到两个子节点

modify()/ update()

u为结点编号,更新该结点的区间最大值

修改--单点修改or区间修改(懒标记)

quary(int u,int l,int r)

查询某段区间的信息

查询以u为节点,区间l,r中的最大值

luogu P3372 【模板】线段树 1



#include<iostream>
using namespace std;
#define endl "\n"
#define int long long
#define rep(i,a,n) for(int i=a;i<=n;i++)s
const int N=1e5+10;
#define lc p<<1
#define rc (p<<1)+1
int w[N];


struct node
{
        int l,r,sum,add;//add->lazy tag
}tr[N*4];

void build(int p,int l,int r)
{
        tr[p]={l,r,w[l],0};//sum在回溯时更新,暂时无意义
        if(l==r)return;//r如果是叶子节点,返回
        //不是叶子节点,分裂
        int m=l+r>>1;
        build(lc,l,m);
        build(rc,m+1,r);
        tr[p].sum=tr[lc].sum+tr[rc].sum;


}

void pushup(int p)
{//向上更新
        tr[p].sum=tr[lc].sum+tr[rc].sum;

}

void pushdown(int p)
{//向下更新
        if(tr[p].add)
        {
                tr[lc].sum+=tr[p].add*(tr[lc].r-tr[lc].l+1);
                tr[rc].sum+=tr[p].add*(tr[rc].r-tr[rc].l+1);
                tr[lc].add+=tr[p].add;
                tr[rc].add+=tr[p].add;
                tr[p].add=0;

        }
}

void update(int p,int x,int y,int k)
{//p父节点编号 xy区间 k修改的值
        if(x<=tr[p].l&&y>=tr[p].r)//覆盖
        {
                tr[p].sum+=k*(tr[p].r-tr[p].l+1);
                tr[p].add+=k;
                return;
        }
        //不覆盖
        int m=tr[p].l+tr[p].r>>1;
        pushdown(p);
        if(x<=m)update(lc,x,y,k);
        if(y>m)update(rc,x,y,k);
        pushup(p);

}



int quary(int p,int x,int y)
{
        if(x<=tr[p].l&&tr[p].r<=y)
        return tr[p].sum;

        int m=tr[p].l+tr[p].r>>1;
        pushdown(p);
        int sum=0;
        if(x<=m)sum+=quary(lc,x,y);
        if(y>m)sum+=quary(rc,x,y);
        return sum;
}



void solve()
{
        int n,q;
        cin>>n>>q;
        rep(i,1,n)cin>>w[i];
        build(1,1,n);

        while(q--)
        {
                int nn;
                cin>>nn;
                if(nn==1)
                {
                        int x,y,k;
                        cin>>x>>y>>k;
                        update(1,x,y,k);

                }
                if(nn==2)
                {
                        int x,y;
                        cin>>x>>y;
                        cout<<quary(1,x,y)<<endl;
                }
        }
        
}
signed main()
{
        ios::sync_with_stdio(false);
    	cin.tie(0),cout.tie(0);
        
        //cout<<"123"<<endl;
        solve();

}

标签:lc,int,线段,tr,add,rc,sum
From: https://www.cnblogs.com/ying-tu/p/17608180.html

相关文章

  • Even(23Nowcoder6.J)(二分+可持久化线段树)
    题意:给定一个序列\(a\),定义一次操作选择序列中一个元素\(a[i]\),使\(a_i=\lfloor\frac{a_i}{2}\rfloor\),其中\(a_i\)为当前序列中的最大偶数,若没有则是最大奇数。有\(q\)组询问,每次给定\(k,l,r\)分别表示操作次数和操作区间,每次回答操作完成后区间中的\(Max\),询问间互相......
  • [Ynoi2012] NOIP2015 充满了希望(扫描线+线段树)
    题目传送门solution简单题。我们正着做扫描线。设\(t_i\)表示位置\(i\)最后一次进行二操作的时间,那么一操作就是交换\(t_x,t_y\),二操作就是区间复制。对于三操作,开一个树状数组,如果查询的位置的\(t_x=j\),就在\(j\)的位置上加一。查询就是查询后缀和。#include<bit......
  • 【复健】线段树
    线段树复健OJ上的题还没做完,下午再说(你概念一种二叉搜索树,通过二叉树形结构储存数据,能够解决大部分与区间操作有关的问题,当然应用范围不止于区间操作。原理是用二分(?)维护一定的区间。主体部分实现建树考虑递归建树,一直二分直到只剩一个数据为止。展开代码inlinevoidpu......
  • [HEOI2013] Segment李超线段树
    RT感觉会模板就差不多了,可用作处理一些线段或直线的问题,转化过来的也可以。比如DP的斜率优化,直线的话只用一个log,线段要两个log。[HEOI2013]Segment模板#include<iostream>usingnamespacestd;constintmod1=39989;constintmod2=1e9;constdoubleesp=1e-9;const......
  • 线段树
    「观前提醒」「文章仅供学习和参考,如有问题请在评论区提出」目录引入基本原理建树区间查询单点修改区间修改+懒惰标记例题P3372【模板】线段树1-洛谷P3373【模板】线段树2-洛谷小结参考资料引入线段树(SegmentTree)是算法竞赛中常用的用来维护区间信息的数据结构......
  • 线段树
    这是洛谷线段树模板题绿标题,线段树好像没什么好总结的,主要看脑子1#include<iostream>2usingnamespacestd;3#defineintlonglong4constintN=1e5+10,inf=0x3f3f3f3f3f3f3f3f;5intn,q,m;6intf[4*N],a[N],lazy1[4*N],lazy2[4*N];7//l......
  • luogu P3733 [HAOI2017] 八纵八横 题解【线段树分治+线性基+可撤销并查集+bitset】
    目录题目大意解题思路code题目大意题目链接给出一张\(n\)个点\(m\)条边的连通无向图,边带边权\(w_i\)。有以下三种操作,共\(q\)次:\(\centerdot\)在点\(x,y\)之间加入一条边权为\(w_i\)的边,如果这是第\(i\)个此种操作,则记这条新边为第\(i\)条。\(\centerdot\)将第\(k......
  • [TJOI2007] 线段
    #[TJOI2007]线段##题目描述在一个$n\timesn$的平面上,在每一行中有一条线段,第$i$行的线段的左端点是$(i,L_{i})$,右端点是$(i,R_{i})$。你从$(1,1)$点出发,要求沿途走过所有的线段,最终到达$(n,n)$点,且所走的路程长度要尽量短。更具体一些说,你在任何时候只能选择向......
  • lazy 线段树代码
    描述 代码:1classNode{2intl,r;3intsum;4intlazy;5}67classSegmentTree{89privateNode[]tree;1011privateint[]nums;1213publicSegmentTree(int[]nums){14intn=nums.length;15......
  • 懒标记线段树
    1.操作符号含义\(nums\)原数组\(d\)线段树节点维护值\(lazytag\)线段树节点懒标记值\(p\)当前节点\(s\)查询区间的开始\(e\)查询区间的结尾\(l\)节点区间的开始\(r\)节点区间的结尾一般习惯:建树从下标\(1\)开始\(mid=(l+......