devbox
知新_RL
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

数据结构——板子_数据结构板子

作者：知新_RL | 2024-08-01 10:51:51

赞

踩

数据结构板子

数据结构

树状数组

单点修改-区间修改

注意1：记得空间初始化为n就可以了，内部自动开辟n+1空间

struct BIT
{
    int n;
    vector<int>vec;
    BIT(int len=0)
    {
        n=len;
        vec.resize(n+1,0);
    }
    int pre(int x)
    {
        int sum=0;
        while(x)
            sum+=vec[x] , x-=lowbit(x);
        return sum;
    }
    void add(int x,int v)
    {
        while(x<=n)
            vec[x]+=v , x+=lowbit(x);
    }
    int segment_sum(int l,int r)
    {
        return pre(r)-pre(l-1);
    }
}; 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

区间修改_单点查询（查询的单点增量）

struct BIT
{
    int n;
    vector<int>vec;
    BIT(int len=0)
    {
        n=len;
        vec.resize(n+1);
    }
    int pre(int pos)
    {
        int sum=0;
        while(pos)
            sum+=vec[pos],pos-=lowbit(pos);
        return sum;
    }
    void add(int pos,int value)
    {
        while(pos<=n)
            vec[pos]+=value,pos+=lowbit(pos);
    }
    void range_add(int l,int r,int value)
    {
        add(l,value),add(r+1,-value);
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26

在这里插入图片描述

区间修改+区间查询

struct Bit
{
    vector<int>sum1,sum2;
    int n;
    Bit(int x=0)
    {
        n=x;
        sum1.resize(n+1);
        sum2.resize(n+1);
    }
    void add(int p,int x)
    {
        for(int i=p;i<=n;i+=lowbit(i))
            sum1[i]+=x,sum2[i]+=x*p;
    }
    void range_add(int l,int r,int x)
    {
        add(l,x),add(r+1,-x);
    }
    int ask(int p)
    {
        int res=0;
        for(int i=p;i;i-=lowbit(i))
            res+=(p+1)*sum1[i]-sum2[i];
        return res;
    }
    int range_ask(int l,int r)
    {
        return ask(r)-ask(l-1);
    }
}; 

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31

在这里插入图片描述
在这里插入图片描述

sum1[i]=d[i] ，sum2[i]=d[i]∗i

线段树

modify(单点改值) query(区间min)

struct SegmentTree1
{
    vector<int>vec;
    SegmentTree(vector<int> &a){
        int n=a.size();
        vec.resize(n<<2);
        function<void(int,int,int)>build=[&](int p,int l,int r){
            if(l==r){
                vec[p]=a[l-1];
                return ;
            }
            int mid=(l+r)>>1;
            build(p*2,l,mid);
            build(p*2+1,mid+1,r);
            up(p);
        };
        build(1,1,n);
    }
    void up(int p){
        vec[p]=min(vec[p*2],vec[p*2+1]);
    }
    void add(int p,int l,int r,int x,int v){
        if(l==r){
            vec[p]=v;
            return ;
        }
        int mid=(l+r)>>1;
        if(x<=mid)
            add(p*2,l,mid,x,v);
        else
            add(p*2+1,mid+1,r,x,v);
        up(p);
    }
    int sum(int p,int l,int r,int x,int y){
        if(x<=l&&r<=y)
            return vec[p];
        int mid=(l+r)>>1,res=inf;
        if(x<=mid)
            res=min(res,sum(p*2,l,mid,x,y));
        if(mid<y)
            res=min(res,sum(p*2+1,mid+1,r,x,y));
        return res;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

modify(区间改值) query(区间min)

struct SegmentTree2
{
    vector<int>s,col;
    SegmentTree2(vector<int> &a){
        int n=a.size();
        s.resize(n*4);
        col.resize(n*4);
        function<void(int,int,int)>build=[&](int p,int l,int r){
            if(l==r){
                s[p]=a[l-1];
                return ;
            }
            int mid=(l+r)>>1;
            build(1,l,mid);
            build(1,mid+1,r);
            up(p);
        };
        build(1,1,n);
    }
    void up(int p){
        s[p]=max(s[p*2],s[p*2+1]);
    }
    void down(int p,int l,int r){
        if(col[p]){
            s[p*2]=col[p];
            s[p*2+1]=col[p];
            col[p*2]=col[p];
            col[p*2+1]=col[p];
            col[p]=0;
        }
    }
    void modify(int p,int l,int r,int x,int y,int v){
        if(x<=l&&r<=y){
            s[p]=v;
            col[p]=v;
            return ;
        }
        down(p,l,r);
        int mid=(l+r)/2;
        if(x<=mid)
            modify(p*2,l,mid,x,y,v);
        if(y>mid)
            modify(p*2+1,mid+1,r,x,y,v);
        up(p);
    }
    int query(int p,int l,int r,int x,int y){
        if(x<=l&&r<=y)
            return s[p];
        down(p,l,r);
        int mid=(l+r)/2,res=0;
        if(x<=mid)
            res=max(res,query(p*2,l,mid,x,y));
        if(y>mid)
            res=max(res,query(p*2+1,mid+1,r,x,y));
        return res;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57

modify(区间±) query(区间min)

struct SegmentTree2
{
    vector<int>s,col;
    SegmentTree2(vector<int> a)
    {
        int n=a.size();
        s.resize(n*4);
        col.resize(n*4);
        function<void(int,int,int)>build=[&](int p,int l,int r)
        {
            if(l==r)
            {
                s[p]=a[l-1];
                return ;
            }
            int mid=(l+r)>>1;
            build(1,l,mid);
            build(1,mid+1,r);
            up(p);
        };
        build(1,1,n);
    }
    void up(int p)
    {
        s[p]=min(s[p*2],s[p*2+1]);
    }
    void down(int p,int l,int r)
    {
        if(col[p])
        {
            int mid=(l+r)>>1;
            solve(p<<1,col[p]);
            solve(p<<1|1,col[p]);
            col[p]=0;
        }
    }
    void solve(int p,int v)
    {
        s[p]+=v;
        col[p]+=v;
    }
    void modify(int p,int l,int r,int x,int y,int v)
    {
        if(x<=l&&r<=y)
        {
            solve(p,v);
            return ;
        }
        down(p,l,r);
        int mid=(l+r)/2;
        if(x<=mid)
            modify(p*2,l,mid,x,y,v);
        if(y>mid)
            modify(p*2+1,mid+1,r,x,y,v);
        up(p);
    }
    int query(int p,int l,int r,int x,int y)
    {
        if(x<=l&&r<=y)
            return s[p];
        down(p,l,r);
        int mid=(l+r)/2,res=inf;
        if(x<=mid)
            res=min(res,query(p*2,l,mid,x,y));
        if(y>mid)
            res=min(res,query(p*2+1,mid+1,r,x,y));
        return res;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69

modify(区间±) query(区间求和)

struct SegmentTree2
{
    vector<int>s,col;
    SegmentTree2(vector<int> &a)
    {
        int n=a.size();
        s.resize(n*4);
        col.resize(n*4);
        function<void(int,int,int)>build=[&](int p,int l,int r)
        {
            if(l==r)
            {
                s[p]=a[l-1];
                return ;
            }
            int mid=(l+r)>>1;
            build(1,l,mid);
            build(1,mid+1,r);
            up(p);
        };
        build(1,1,n);
    }
    void down(int p, int l, int r)
    {
        if (col[p])
        {
            int mid = l + r >> 1;
            solve(p<<1,l,mid,col[p]);
            solve(p<<1|1,mid+1,r,col[p]);
            col[p] = 0;
        }
    }
    void up(int p)
    {
        s[p] = s[p * 2] + s[p * 2 + 1];
    }
    void solve(int p,int l,int r,int value)
    {
        s[p] += (r - l + 1) * value;
        col[p] += value;
    }
    void modify(int p, int l, int r, int L, int R, int value)
    {
        if (L <= l && r <= R)
        {
            solve(p,l,r,value);
            return ;
        }
        down(p, l, r);
        int mid = l + r >> 1;
        if (L <= mid)
            modify(p * 2, l, mid, L, R, value);
        if (mid < R)
            modify(p * 2 + 1, mid + 1, r, L, R, value);
        up(p);
    }
    int query(int p, int l, int r, int L, int R)
    {
        if (L <= l && r <= R)
            return s[p];
        down(p, l, r);
        int mid = l + r >> 1, sum = 0;
        if (L <= mid)
            sum += query(p * 2, l, mid, L, R);
        if (mid < R)
            sum += query(p * 2 + 1, mid + 1, r, L, R);
        s[p] = s[p * 2] + s[p * 2 + 1];
        return sum;
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70

·在这里插入图片描述

ST（nlogn）

一种可重复贡献的数据结构，满足结合律。
类似问题：区间最值，区间按位与，区间按位或

倍增RMQ
第一步：构造RMQ,变量为n。
第二步：记得ST表值初始化为inf/-inf，以及2^0倍赋值和转移方程的max/min修改

struct RMQ
{
    vector<vector<int> >ST;
    RMQ(int n=0)
    {
        ST.resize(n+1,vector<int>(21,inf));
        for(int i=1;i<=n;i++)
            ST[i][0]=pre[i];
        for(int i=1;(1<<i)<=n;i++)
            for(int j=1;j+(1<<i)-1<=n;j++)
                ST[j][i]=min(ST[j][i-1],ST[j+(1<<i-1)][i-1]);
    }
    int query(int l,int r)
    {
        int k=log2(r-l+1);
        return min(ST[l][k],ST[r-(1<<k)+1][k]);
    }
};

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18

分块

const int N=5e4+5;
int a[N],n,m,num,block;
int l[N],r[N],belong[N],tag[N];
void init()
{
    block=sqrt(n);
    num=ceil(n*1.0/block);
    for(int i=1;i<=num;i++)
        l[i]=(i-1)*block+1,r[i]=i*block;
    r[num]=n;
    for(int i=1;i<=n;i++)
        belong[i]=(i-1)/block+1;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13

莫队（ n n n\sqrt n nn ​）

离线（特别注意卡常，一般处理1e5,1e6直接上BIT）

const int N=1e6+5;
int a[N],cnt[N],belong[N],block,sum=0,ans[N];
struct node
{
    int l,r,pos;
    bool operator<(const node &b)const
    {
          return belong[l]==belong[b.l]?r<b.r:belong[l]<belong[b.l];
    }
} s[N];
void add(int pos)
{
    if(!cnt[a[pos]])
        ++sum;
    ++cnt[a[pos]];
}
void del(int pos)
{
    --cnt[a[pos]];
    if(!cnt[a[pos]])
        --sum;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22

进行分块

block=sqrt(n);
    for(int i=1; i<=n; ++i)
        belong[i]=(i-1)/block+1;

  • 1
  • 2
  • 3

双指针移动

    int l=1,r=0;
	for(int i=0; i<m; ++i)
    {
        int ql=s[i].l,qr=s[i].r;
        while(l<ql)
            del(l++);
        while(l>ql)
            add(--l);
        while(r<qr)
            add(++r);
        while(r>qr)
            del(r--);
        ans[s[i].pos]=sum;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14

卡常优化

1：移动指针常数优化，大概200ms

        while(l < ql)
            sum -= !--cnt[a[l++]];
        while(l > ql)
            sum += !cnt[a[--l]]++;
        while(r < qr)
            sum += !cnt[a[++r]]++;
        while(r > qr)
            sum -= !--cnt[a[r--]];

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8

2：玄学奇偶性排序，大概200ms

return (belong^b.belong)?belong<b.belong:((belong&1)?r<b.r:r> b.r);

  • 1

玄学

	bool operator<(const node& b)
    {
        if(belong==b.belong)
            return r<b.r;
        return l<b.l;
    }

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6

3：快读，快输优化

int read()
{
    int res = 0;
    char c = getchar();
    while(!isdigit(c))
        c = getchar();
    while(isdigit(c))
        res = (res << 1) + (res << 3) + c - 48, c = getchar();
    return res;
}
void printi(int x)
{
    if(x / 10)
        printi(x / 10);
    putchar(x % 10 + '0');
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16

4：分块优化
O( n 2 3 n^{\frac2 3} n32​)

int num=n/sqrt(m*2.0/3);

  • 1

5：开O2

主席树（可持久化线段树维护区间权值和）

const int N=5e5+5;
namespace zhuxi
{
    struct node
    {
        int left,right,value;
    }s[N*40];
    int cnt=0,root[N];
    void modify(int l,int r,int pre,int &now,int value)
    {
        s[++cnt]=s[pre];
        now=cnt;
        s[cnt].value++;
        if(l==r)
            return ;
        int mid=(l+r)>>1;
        if(value<=mid)
            modify(l,mid,s[pre].left,s[now].left,value);
        else
            modify(mid+1,r,s[pre].right,s[now].right,value);
    }
    int query(int l,int r,int L,int R,int k)
    {
        if(l==r)
            return l;
        int mid=(l+r)>>1;
        int temp=s[s[R].left].value-s[s[L].left].value;
        if(k<=temp)
            return query(l,mid,s[L].left,s[R].left,k);
        else
            return query(mid+1,r,s[L].right,s[R].right,k-temp);
    }
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33

可持久化并查集（只会板子）

const int N =2e5+5;
int n,m,root[N],cnt;
struct node
{
    int l,r,fat,Size;
} s[N*30];
void build(int& p,int l,int r)
{
    p=++cnt;
    if(l==r)
    {
        s[p].fat=l;
        s[p].Size=1;
        return;
    }
    int mid=l+r>>1;
    build(s[p].l,l,mid);
    build(s[p].r,mid+1,r);
}
pair<int,int> query(int p,int l,int r,int pos)
{
    if(l==r)
        return {s[p].fat,s[p].Size};
    int mid=l+r>>1;
    if(pos<=mid)
        return query(s[p].l,l,mid,pos);
    else
        return query(s[p].r,mid+1,r,pos);
}
void update(int pre,int &p,int l,int r,int pos,int Fat,int sum)
{
    p=++cnt;
    s[p]=s[pre];
    if(l==r)
    {
        s[p].Size=sum;
        s[p].fat=Fat;
        return;
    }
    int mid=l+r>>1;
    if (pos<=mid)
        update(s[pre].l,s[p].l,l,mid,pos,Fat,sum);
    else
        update(s[pre].r,s[p].r,mid+1,r,pos,Fat,sum);
}
pair<int,int> find(int root,int pos)
{
    pair<int,int> ans=query(root,1,n,pos);
    if (ans.F==pos)
        return ans;
    else
        return find(root,ans.F);
}
int main()
{
    cin>>n>>m;
    build(root[0], 1, n);///初始化
    for (int i=1;i<=m;i++)
    {
        int ty;
        cin>>ty;
        if(ty==1)///x-y合并
        {
            root[i]=root[i-1];
            int x,y;
            cin>>x>>y;
            pair<int,int> tx=find(root[i],x);
            pair<int,int> ty=find(root[i],y);
            if(tx.F==ty.F)
                continue;//已经是一起的
            if(tx.S>ty.S)
                swap(tx,ty);
            update(root[i],root[i],1,n,tx.F,ty.F,0);
            update(root[i],root[i],1,n,ty.F,ty.F,tx.S+ty.S);
        }
        else if(ty==2)///操作i回到x版本
        {
            int x;
            cin>>x;
            root[i]=root[x];
        }
        else///判断x与y是否同一集合
        {
            root[i]=root[i-1];
            int x,y;
            cin>>x>>y;
            cout<<(find(root[i],x)==find(root[i], y))<<endl;
        }
    }
    return 0;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59
  • 60
  • 61
  • 62
  • 63
  • 64
  • 65
  • 66
  • 67
  • 68
  • 69
  • 70
  • 71
  • 72
  • 73
  • 74
  • 75
  • 76
  • 77
  • 78
  • 79
  • 80
  • 81
  • 82
  • 83
  • 84
  • 85
  • 86
  • 87
  • 88
  • 89
  • 90
  • 91
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/知新_RL/article/detail/913682
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号