线段树小寄巧

· · 算法·理论

我是标题党

其实就是课上想到的一个缩小线段树空间的一个编号方式而已。挺唐的。

当然了，只是一个比较无用的东西，相比于 zkw 还是逊色了许多。只是觉得有意思写一下玩的。（叠甲）

大体介绍

其实也没啥。

这个方式可以将线段树正常的 4N 空间缩小到 2N 且与普通递归线段树写法基本无差异。

我们都能发现，其实线段树的编码被大量浪费了。

而我们发现对于一个长度为 n 的序列建立线段树会有 2n-1 个节点，而其中有 n 个节点都是在最后一层的。

所以我们考虑先处理前 n-1 个节点，即直接令其节点编号为其表示区间 [l,r] 的 mid=\left \lfloor \frac{l+r}{2} \right \rfloor 即可。

因为我们发现对于非最后一层的点的点的区间的 mid 不会重复。

而对于最底层的 n 个节点我们令其节点编号为 n+l 即可，当然了如果区间包含负数或者其他特殊情况这种方式就不能用了。

线段树模板 P3372 AC 记录：https://www.luogu.com.cn/record/252184715

写法上其实就是只用多写一个函数。

而这种方式在递归的时候不需要下传节点编号，所以会快一点。

inline int son(int l,int r){
  return (l==r)?(n+l):(mid);
}

当然了，您如果觉得函数慢也可以改为 define 啦。

观察到代码中只开了 s[(N<<1)],t[(N<<1)] 所以只有 2N 的空间。

我能想到的应用场景就是在 zkw 线段树用不了且不能用树状数组代替的时候帮助你卡常。

code

//Author:Kevin Z K Y
#include <bits/stdc++.h>
#define up(a,b,c) for(int (a)=(b);(a)<=(c);(a)++)
#define dn(a,b,c) for(int (a)=(b);(a)>=(c);(a)--)
#define fst first
#define sed second
#define Max(x,y) (((x)>(y))?(x):(y))
#define Min(x,y) (((x)<(y))?(x):(y))
#define Abs(x) (((x)<0)?(-(x)):(x))
using namespace std;
using us = unsigned short ;using ldb = long double ;
using ull = unsigned long long ;using ui = unsigned int ;
using ll = long long ;using hint = __int128 ;
using pii = pair<int,int> ;using pll = pair<ll,ll> ;
using pil = pair<int,ll> ;using vpil = vector<pil> ;
using pli = pair<ll,int> ;using vpli = vector<pli> ;
using vi = vector<int> ;using vl = vector<ll> ;
using vpi = vector<pii> ;using vpl = vector<pll> ;
using db = double ;namespace mystl{
    #define gc() p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<12,stdin),p1==p2)?EOF:*p1++
    char buf[1<<20], *p1=buf, *p2=buf, sr[1<<23], z[23], nc;int C=-1 ,Z=0;
    template <typename T> inline void read ( T & x ) { bool flag = false ;
        while( nc = gc() ,(nc<48||nc>57) && nc!=-1)flag|=(nc==45);x=nc-48;
        while(nc=gc(),47<nc&&nc<58)x=(x<<3)+(x<<1)+(nc^48); if(flag)x=-x;}
    inline void ot(  )  {  fwrite( sr , 1 , C + 1, stdout ) ;  C = - 1 ; }
    inline void flush( ) { if ( C > 1<<22 ) ot() ; } template <typename T>
    inline void write(T x,char t){ int y = 0 ; if ( x < 0 ) y = 1, x = -x;
        while( z [ ++ Z ] = x % 10 + 48 , x /= 10) ; if( y ) z[ ++Z ]='-';
        while( sr[ ++ C ] = z[ Z ] , -- Z ) ; sr [ ++C ] = t ; flush() ; }
    inline ll qpow(ll a , ll b , ll p) { if (a==0ll) return 0ll; ll c=1ll;
              while(b) { if(b & 1) c=a*c%p; a=a*a%p; b>>=1; } return c ; }
    void exgcd ( ll a , ll b , ll & cx , ll & cy){if(a % b==0)cx = 0,cy=1;
                else { exgcd( b , a % b , cy , cx) ; cy -= a / b * cx ; }}
    inline ll lcm ( ll x , ll y ){return x / std :: __gcd( x , y ) * y ; }
}using namespace mystl;
namespace my{
    const int N=(int)(1e5+5),P=(int)(998244353);
    const int inf=(int)(1e9);
    int n,Q;
    ll s[(N<<1)],t[(N<<1)];
    #define mid (((l)+(r))>>1)
    inline int son(int l,int r){
        return (l==r)?(n+l):(mid);
    }
    inline void pushup(int l,int r,int p){
        s[p]=s[son(l,mid)]+s[son(mid+1,r)];
    }
    inline void add_tag(int l,int r,ll x,int p){
        s[p]+=1ll*(r-l+1)*x;
        t[p]+=x;    
    }
    inline void pushdown(int l,int r,int p){
        if(!t[p])return ;
        add_tag(l,mid,t[p],son(l,mid));
        add_tag(mid+1,r,t[p],son(mid+1,r));
        t[p]=0;
    }
    void build(int l,int r,int p){
        if(l==r){
            read(s[p]);
            return ;
        }
        build(l,mid,son(l,mid));
        build(mid+1,r,son(mid+1,r));
        pushup(l,r,p);
    }
    void add(int l,int r,int L,int R,ll x,int p){
        if(L<=l&&r<=R){
            add_tag(l,r,x,p);
            return ;
        }
        pushdown(l,r,p);
        if(L<=mid)add(l,mid,L,R,x,son(l,mid));
        if(R>mid)add(mid+1,r,L,R,x,son(mid+1,r));
        pushup(l,r,p);
    }
    ll ask(int l,int r,int L,int R,int p){
        if(L<=l&&r<=R)return s[p];
        pushdown(l,r,p);
        ll ret=0;
        if(L<=mid)ret+=ask(l,mid,L,R,son(l,mid));
        if(R>mid)ret+=ask(mid+1,r,L,R,son(mid+1,r));
        return ret;
    }
    inline void SOLVE(){
        read(n);read(Q);
        build(1,n,(1+n)/2);
        while(Q--){
            int op,l,r;
            read(op);read(l);read(r);
            if(op==1){
                ll x;read(x);
                add(1,n,l,r,x,(1+n)/2);
            }
            else write(ask(1,n,l,r,(1+n)/2),'\n');
        }
        ot();
    }
}
int main(){
//  freopen("","r",stdin);
//  freopen("","w",stdout);
    ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);
    int _=1;while(_--)my::SOLVE();return 0;
}
/*

*/