CVBB ACM Team

本页面只读。您可以查看源文件，但不能更改它。如果您觉得这是系统错误，请联系管理员。
====== 前言 ======
用处与一维线段树类似，实现区间的修改、查询工作，知识是在二维的区域中实现的。
====== 两种实现方式 ======
  * 普通列表项目每一个节点代表一颗线段树
{{:2020-2021:teams:no_morning_training:shaco:知识点:数据结构:0.5935530263444292.png?200|}}
  * 普通列表项目四分法转为一维线段树
{{:2020-2021:teams:no_morning_training:shaco:知识点:数据结构:0.7330317843697223.png?200|}}
====== 复杂度 ======
空间复杂度都是$O(n^2\times log_n^2)$。
第一种方法单次操作时间复杂度为$O(log_n^2)$，第二种方法最差可以退化到$O(n)$。
这里介绍第一种方法。思想主要是在二维的区间中将包含目标小区间的区间全部修改，类似于一维情况。
====== 操作 ======
===== 单点修改+矩阵查询 =====
==== 修改 ====
<hidden code>
<code cpp>
void changex(int kx,int l,int r)
{
    changey(kx,1,1,h);
    if(l==r) return;
    int mid=l+r>>1;
    if(x<=mid) changex(kx<<1,l,mid);
    else changex(kx<<1|1,mid+1,r);
}
void changey(int kx,int ky,int l,int r) //方法一
{
    sum[kx][ky]++;
    if(l==r) return;
    int mid=l+r>>1;
    if(y<=mid) changey(kx,ky<<1,l,mid);
    else changey(kx,ky<<1|1,mid+1,r);
}
void changey(int kx,int ky,int l,int r) //方法二
{
    if(l==r)
    {
        sum[kx][ky]++;
        return;
    }
    int mid=l+r>>1;
    if(y<=mid) changey(kx,ky<<1,l,mid);
    else changey(kx,ky<<1|1,mid+1,r);
    sum[kx][ky]=sum[kx][ky<<1]+sum[kx][ky<<1|1];
}
</code>
</hidden>
==== 查询 ====
<hidden code>
<code cpp>
void queryy(int kx,int ky,int l,int r)
{
    if(l>=yl && r<=yr)
    {
        cnt+=sum[kx][ky];
        return;
    }
    int mid=l+r>>1;
    if(yl<=mid) queryy(kx,ky<<1,l,mid);
    if(yr>mid) queryy(kx,ky<<1|1,mid+1,r);
}

void queryx(int kx,int l,int r)
{
    if(l>=xl && r<=xr)
    {
        queryy(kx,1,1,h);
        return;
    }
    int mid=l+r>>1;
    if(xl<=mid) queryx(kx<<1,l,mid);
    if(xr>mid) queryx(kx<<1|1,mid+1,r);
}

</code>
</hidden>
===== 矩阵修改+单点查询 =====
==== 修改 ====
<hidden code>
<code cpp>
void changey(int kx,int ky,int l,int r)
{
    if(y1<=l&&r<=y2)
    {
        sum[kx][ky]++;
        return;
    }
    int mid=l+r>>1;
    if(y1<=mid) changey(kx,ky<<1,l,mid);
    if(y2>mid) changey(kx,ky<<1|1,mid+1,r);
}
void changex(int kx,int l,int r)
{
    if(x1<=l&&r<=x2)
    {
        changey(kx,1,1,n);
        return;
    }
    int mid=l+r>>1;
    if(x1<=mid) changex(kx<<1,l,mid);
    if(x2>mid) changex(kx<<1|1,mid+1,r);
}

</code>
</hidden>
==== 查询 ====
<hidden code>
<code cpp>
void queryy(int kx,int ky,int l,int r)
{
    ans+=sum[kx][ky];
    if(l==r) return;
    int mid=ly+ry>>1;
    if(y<=mid) queryy(kx,ky<<1,l,mid);
    else queryy(kx,ky<<1|1,mid+1,r);
}
void queryx(int kx,int l,int r)
{
    queryy(kx,1,1,n);
    if(l==r) return;
    int mid=l+r>>1;
    if(x<=mid) queryx(kx<<1,l,mid);
    else queryx(kx<<1|1,mid+1,r);
}

</code>
</hidden>
====== 参考 ======
[[https://www.cnblogs.com/TheRoadToTheGold/p/8151375.html]]
CVBB ACM Team

用户工具

站点工具

页面工具
