蓝桥杯 第五讲 树状数组和线段树 2D/3D差分

2023-10-07 13:16:28

一、树状数组 下标从1开始

操作 O(logn)

  1. 单点修改： 给某个位置上的数加上一个数
  2. 区间查询：求某一个前缀和

离线做法：不支持修改
在线做法：支持修改

原理

蓝桥杯 第五讲 树状数组和线段树 2D/3D差分

层数的确定：x的二进制表示中末尾有几个0
c[x] = (x-lowbit(x),x]的和
lowbit(x):返回x的二进制表达式中最低位的1所对应的值
lowbit(6) = 2,因为(110)2中最低位（就是从右往左数的第二位）对应的数是21=2
1264. 动态求连续区间和

#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 100005;

int a[N],n,m;
int tr[N];//tr[x]表示(x-lowbit(x),x]的和
int k,x,y;
int lowbit(int x)
{
    return x & -x;
}
void add(int x,int v) //第x的位置上加上一个数
{
    for(int i = x;i <= n;i+=lowbit(i))
    {
        tr[i] += v;
    }
}
int query(int x) //查询 1~x的前缀和
{
    int res = 0;
    for(int i = x;i>=1;i-=lowbit(i))
    {
        res += tr[i];
    }
    return res;
}
int main()
{
    scanf("%d%d",&n,&m);
    for (int i = 1; i <= n; i ++ ) //切记下标要从1开始
    {
        scanf("%d", &a[i]);
        add(i,a[i]);
    }
    while (m -- )
    {
        scanf("%d%d%d",&k,&x,&y);
        if(k==0)
        {
            cout<<query(y) - query(x-1)<<endl; //前缀和思想
        }
        else add(x,y);
    }
    return 0;
}

1265. 数星星
由于坐标按照y升序给出，故当前星星的坐标一定大于等于之前任何星星，故需要统计小于等于当前星星的x的个数，即为左下方星星个数

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 32005;
int n,x,y;
int tr[N];//x坐标小于等于i的星星的个数
int level[N];//不同等级星星的个数
int lowbit(int x)
{
    return x & -x;
}
void add(int t,int x)
{
    for(int i=t;i<=N;i+=lowbit(i)) //注意：此处范围是[t,N],x的取值会比n大，WA了好几发
    {
        tr[i] += x;
    }
}
int query(int t)
{
    int sum = 0;
    for(int i=t;i>=1;i-=lowbit(i))
    {
        sum += tr[i];
    }
    return sum;
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++) //由于坐标按照y升序给出，故当前星星的坐标一定大于等于之前任何星星，故需要统计小于等于当前
    //星星的x的个数，即为左下方星星个数
    {
        scanf("%d%d", &x, &y);
        x++;//将x映射到1~N+1,便于使用树状数组
        level[query(x)]++;
        add(x,1);
    }
    for (int i = 0; i < n; i ++ ) //注意：此处范围为0~n-1，不可能有等级为n的星星
    {
        cout<<level[i]<<endl;
    }
    return 0;
}

二、线段树

以求区间和为例
蓝桥杯 第五讲 树状数组和线段树 2D/3D差分

核心操作 O(logn)

1. 单点修改

递归地进行修改，只要此区间包含要修改的点，就修改区间的sum

2. 区间查询

递归地查询，只要该区间的[l,r]被目标区间完全包含，则累加并回溯，否则继续向下递归查询。
查询次数小于等于4logn
蓝桥杯 第五讲 树状数组和线段树 2D/3D差分

主要函数

pushup用子节点信息更新当前结点信息
build在一段区间上初始化线段树
modify修改
query查询
pushdown懒标记
1264. 动态求连续区间和

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1e5+10;

int n,m,k,a,b;
int w[N];

struct Node
{
    int l;
    int r;
    int sum;
}tr[N*4]; //线段树最大结点个数为4N

void pushup(int u) //用左右儿子结点信息更新根结点信息
{
    tr[u].sum = tr[2*u].sum + tr[2*u+1].sum;
}

void build(int u,int l,int r) //形参解释：u表示根结点，l,r表示原始数据区间的左右端点
{
    if(l==r) tr[u] = {l,r,w[r]};//区间元素个数为1，是叶结点，直接赋值返回
    else
    {
        tr[u] = {l,r};//注意：此处一定要赋初值
        int mid = l+r>>1;
        build(u*2,l,mid),build(u*2+1,mid+1,r);//递归建立左右儿子区间
        pushup(u);//一定不要忘记更新根结点sum值，将信息向上传递
    }
}
int query(int u,int l,int r)//形参解释：u表示根结点，l,r表示目标区间的左右端点
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].sum; //如果当前区间被目标区间完全包含，则返回当前区间sum
    
    int mid = tr[u].l+tr[u].r>>1;
    int sum = 0;
    if(l <= mid) sum += query(u*2,l,r); //如果目标区间的左边界≤mid，说明和左半边有交集
    if(r > mid) sum += query(u*2+1,l,r);//如果目标区间的右边界＞mid，说明和右半边有交集
    return sum;
}
void modify(int u,int x,int v) //形参解释：u表示根结点，x表示元素下标，v表示要添加的值
{
    if(tr[u].l == tr[u].r) //若走到叶结点，说明已经找到x对应树中的位置，直接修改即可
    {
        tr[u].sum += v;
    }
    else
    {
        int mid = tr[u].l + tr[u].r >> 1;
        if(x <= mid) modify(u*2,x,v);//如果和左半边有交集，就去左半边修改
        else modify(u*2+1,x,v);//如果和右半边有交集，就去右半边修改
        pushup(u);//注意：最后一定要用儿子结点信息更新根结点信息
    }
}
int main()
{
    scanf("%d%d", &n,&m);
    for(int i = 1;i<=n;i++)
    {
        scanf("%d", &w[i]);
    }
    build(1,1,n);
    while (m -- )
    {
        scanf("%d%d%d",&k,&a,&b);
        if(k==0)
        {
            cout<<query(1,a,b)<<endl;
        }
        else modify(1,a,b);
    }
    return 0;
}

1270. 数列区间最大值

#include <iostream>
#include <cstring>
#include <algorithm>
#include <climits>
using namespace std;

const int N = 1e5 + 10;
int w[N];
int n,m,x,y;
struct Node
{
    int l;
    int r;
    int Max;
}tr[N*4];
inline void build(int u,int l,int r)
{
    if(l==r) tr[u] = {l,r,w[r]};
    else
    {
        tr[u] = {l,r};
        int mid = l+r>>1;
        build(u<<1,l,mid),build(u<<1|1,mid+1,r);
        tr[u].Max = max(tr[u<<1].Max,tr[u<<1|1].Max);
    }
}

inline int query(int u,int l,int r)
{
    if(tr[u].l >= l && tr[u].r <= r) return tr[u].Max;
    
    int Max = INT_MIN;
    int mid = tr[u].l + tr[u].r>>1;
    if(l <= mid) Max = max(Max,query(u<<1,l,r));
    if(r > mid) Max = max(Max,query(u<<1|1,l,r));
    return Max;
}
int main()
{
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; i ++ )
    {
        scanf("%d", &w[i]);
    }
    build(1,1,n);
    while (m -- )
    {
        scanf("%d%d",&x,&y);
        printf("%d\n",query(1,x,y));
    }
    return 0;
}

三、2D/3D差分

二维差分

蓝桥杯 第五讲 树状数组和线段树 2D/3D差分
798. 差分矩阵

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;

const int N = 1005;

int b[N][N];
int n,m,q;

void insert(int x1,int y1,int x2,int y2,int c) //x2,y2一定要加1
{
    b[x1][y1] += c;
    b[x2+1][y2+1] += c;
    b[x1][y2+1] -= c;
    b[x2+1][y1] -= c;
}
int main()
{
    scanf("%d%d%d", &n, &m,&q);
    int c;
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            scanf("%d", &c);
            insert(i,j,i,j,c);
        }
    }
    while (q -- )
    {
        int x1,y1,x2,y2;
        scanf("%d%d%d%d%d", &x1, &y1,&x2,&y2,&c);
        insert(x1,y1,x2,y2,c);
    }
    for (int i = 1; i <= n; i ++ )//求前缀和，即将差分矩阵转化为原矩阵
    {
        for (int j = 1; j <= m; j ++ )
        {
            b[i][j] = b[i-1][j] + b[i][j-1] - b[i-1][j-1] + b[i][j];
        }
    }
    for (int i = 1; i <= n; i ++ )
    {
        for (int j = 1; j <= m; j ++ )
        {
            printf("%d ",b[i][j]);
        }
        puts("");
    }
    return 0;
}

三维差分

蓝桥杯 第五讲 树状数组和线段树 2D/3D差分

公式中对于S来说，奇数个减一的符号为正，偶数个减一的符号为负

四、习题

1215. 小朋友排队
本题需要求每个数的逆序对的个数，然后逐一使用等差数列求和公式算出答案即可，求逆序对的数量时需要用到线段树

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;

const int N = 1e6 + 10;

int h[N],tr[N],n;//线段树记录每个数的个数
int sum[N];
int lowbit(int x)
{
    return x & -x;
}
int query(int p)
{
    int sum = 0;
    for(int i=p;i>=1;i-=lowbit(i))
    {
        sum += tr[i];
    }
    return sum;
}
void add(int p,int x)
{
    for(int i=p;i<=N;i+=lowbit(i))
    {
        tr[i]+=x;
    }
}
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d", &h[i]);
        ++h[i];//计算前缀和，需要映射到1~N+1
    }
    for(int i=0;i < n;i++) //求每个数前面有多少个数比它大
    {
        sum[i] += query(N-1) - query(h[i]);
        add(h[i],1);
    }
    memset(tr,0,sizeof tr);//记得将线段树清零
    for (int i = n-1; i >=0 ; i -- )//求每个数后面有多少个数比它小
    {
        sum[i] += query(h[i]-1);
        add(h[i],1);
    }
    LL ans = 0;//答案可能爆int
    for(int i = 0;i<n;i++)
    {
        //cout<<sum[i]<<" ";
        ans += (LL)(1+sum[i])*sum[i]/2;
    }
    cout << ans<<endl;
    return 0;
}

1228. 油漆面积

#include <iostream>
#include <cstring>
#include <algorithm>

using namespace std;
typedef long long LL;
const int N = 10005;

int x1,y1,x2,y2,n;
LL ans;
bool g[N][N];
int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i ++ )
    {
        scanf("%d%d%d%d", &x1, &y1,&x2,&y2);
        for(int j=x1;j<x2;j++)
        {
            for(int k=y1;k<y2;k++) 
            {
                if(!g[j][k])
                {
                    g[j][k] = 1;
                    ++ans;
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}

1232. 三体攻击

上一篇：win10与linux以太坊客户端Geth私链搭建教程


下一篇：4.2以太坊（ETH）操作及解套建议附点位