各个算法模板大全

· · 个人记录

各个算法模板大全

（收集中）

1. 线段树

注释

l 表示区间左端点，r表示区间右端点，s表示线段树左端点，t表示线段树右端点，p表示当时所在点的下标。

注意

线段树一定要开4倍内存！

建树操作

void build(int s,int t,int p) 
{
    if(s==t)
    {
        d[p]=a[s];//a是输入数组
        return;
    }
    int m=s+((t-s)>>1);
    build(s,m,p*2),build(m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}

带懒惰标记的区间更新（加法）

void update(int l,int r,int c,int s,int t,int p)
{
    if(l<=s&&t<=r)
    {
        d[p]+=(t-s+1)*c,b[p]+=c;
        return;
    }
    int m=s+((t-s)>>1);
    if(b[p]&&s!=t)
    {
        d[p*2]+=b[p]*(m-s+1),d[p*2+1]+=b[p]*(t-m);
        b[p*2]+=b[p],b[p*2+1]+=b[p];
        b[p]=0;
    }
    if(l<=m) update(l,r,c,s,m,p*2);
    if(r>m) update(l,r,c,m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}

不带懒惰标记的区间查询

int getsum(int l,int r,int s,int t,int p)
{
    if(l<=s&&t<=r) return d[p];
    int m=s+((t-s)>>1),sum=0;
    if(l<=m) sum+=getsum(l,r,s,m,p*2);
    if(r>m) sum+=getsum(l,r,m+1,t,p*2+1);
    return sum;
}

带懒惰标记的区间查询

int getsum1(int l,int r,int s,int t,int p)
{
    if(l<=s&&t<=r) return d[p];
    int m=s+((t-s)>>1),sum=0;
    if(b[p]&&s!=t)
    {
        d[p*2]+=b[p]*(m-s+1),d[p*2+1]+=b[p]*(t-m);
        b[p*2]+=b[p],b[p*2+1]+=b[p];
        b[p]=0;
    }
    if(l<=m) sum+=getsum(l,r,s,m,p*2);
    if(r>m) sum+=getsum(l,r,m+1,t,p*2+1);
    return sum;
}

带懒惰标记的区间修改

void update_change(int l,int r,int c,int s,int t,int p)
{
    if(l<=s&&t<=r)
    {
        d[p]=(t-s+1)*c,b[p]=c;
        return;
    }
    int m=s+((t-s)>>1);
    if(b[p]&&s!=t)
    {
        d[p*2]=b[p]*(m-s+1),d[p*2+1]=b[p]*(t-m);
        b[p*2]=b[p],b[p*2+1]=b[p];
        b[p]=0;
    }
    if(l<=m) update(l,r,c,s,m,p*2);
    if(r>m) update(l,r,c,m+1,t,p*2+1);
    d[p]=d[p*2]+d[p*2+1];
}

带懒惰标记的区间更新（加法+乘法）

void pushdown(int s,int t,int p)//mod是取余数
{
    int m=s+((t-s)>>1);
    d[2*p]=(d[2*p]*b1[p]+(m-s+1)*b[p])%mod;
    d[2*p+1]=(d[2*p+1]*b1[p]+(t-m)*b[p])%mod;
    b1[2*p]=(b1[2*p]*b1[p])%mod;
    b1[2*p+1]=(b1[2*p+1]*b1[p])%mod;
    b[2*p]=(b[p*2]*b1[p]+b[p])%mod;
    b[2*p+1]=(b[2*p+1]*b1[p]+b[p])%mod;
    b1[p]=1;
    b[p]=0;
}
void add(int l,int r,long long c,int s,int t,int p)
{
    if(l<=s&&t<=r)
    {
        d[p]=(d[p]+(t-s+1)*c%mod)%mod,b[p]=(b[p]+c%mod)%mod;
        return;
    }
    int m=s+((t-s)>>1);
    pushdown(s,t,p);
    if(l<=m) add(l,r,c,s,m,p*2);
    if(r>m) add(l,r,c,m+1,t,p*2+1);
    d[p]=(d[p*2]+d[p*2+1])%mod;
}
void multi(int l,int r,long long c,int s,int t,int p)
{
    if(l<=s&&t<=r)
    {
        d[p]=(d[p]*c)%mod;
        b1[p]=(b1[p]*c)%mod;
        b[p]=(b[p]*c)%mod;
        return;
    }
    int m=s+((t-s)>>1);
    pushdown(s,t,p);
    if(l<=m) multi(l,r,c,s,m,p*2);
    if(r>m) multi(l,r,c,m+1,t,p*2+1);
    d[p]=(d[p*2]+d[p*2+1])%mod;
}

练习题

模板Ⅰ

模板Ⅱ

2.树状数组

基本核心：lowbit函数

基本定义：

一个数的二进制表达式中最低位的1以及其后的0组成的数所对应的值。

e.g.

\because(17)_{10}=(1000\color{red}1\color{black})_2 \therefore lowbit(17)=(1)_2=(1)_{10}

图表示例

如图所示，d[2]所储存的值是d[1]+a[2]，且d[2]的lowbit值为2。

int lowbit(int x)
{
    return x&-x;
}

修改单个结点值（加法）

void add(int x,int k)
{
    while(x<=n)//n为最右点
    {
        c[x]+=k;
        x+=lowbit(x);
    }
}

查询第1~x项结点值之和

int getsum(int x)
{
    int ans=0;
    while(x>=1)
    {
        ans+=c[x];
        x-=lowbit(x);
    }
    return ans;
}

差分数组

如图所示，差分数组b每项的值是a数组每项的差值。其公式为：

b_i=a_i-a_{i-1}(1\leqslant i \leqslant n)

在修改一个区间的结点值时，就可以使用差分数组进行运算。

e.g.

下标 0 1 2 3 4
a 0 1 2 4 1
b 0 1 1 2 -3

要求[1,3]区间数值加一：

下标 0 1 2 3 4
a 0 1+1 2+1 4+1 1
b 0 1+1 1 2 -3-1

发现了吗？只有b[1]与b[4]的值变化了。

结论：当区间[l,r]加上一个值k时：

b_l+=k,b_{r+1}-=k(1 \leqslant l \leqslant r < n)

修改区间结点值（加法，差分数组）

void _add(int x,int k)
{
    int v=x*k;
    while(k<=n)
    {
        t1[x]+=k;
        t2[x]+=v;//(i-1)*b_i数组 
        x+=lowbit(x);
    }
}
void add1(int l,int r,int v)//使用时调用此处
{
    _add(l,v);
    _add(r+1,-v);
}

查询区间结点值之和（差分数组）

int _getsum(int *t,int x)
{
    int ans=0;
    while(x)
    {
        ans+=t[x];
        x-=lowbit(x);
    }
    return ans;
}
long long getsum1(int l,int r)
{
    return(r+1ll)*_getsum(t1,r)-1ll*l*_getsum(t1,l-1)-(_getsum(t2,r)-_getsum(t2,l-1));
}

练习题

模板Ⅰ

模板Ⅱ