【ybt】【数据结构 树状数组 课过 例6】区间修改区间查询

2024-01-30 03:18

本文主要是介绍【ybt】【数据结构 树状数组 课过 例6】区间修改区间查询,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

区间修改区间查询

题目链接:YbtOJ


在这里插入图片描述

解题思路

我们可以把区间修改区间查询的差分与单点修改区间查询结合起来,也就是二维树状数组维护二维前缀和再加上差分。

code

#include<iostream>
#include<cstdio>
#define lb(x) (x&(-x))
#define int long long
using namespace std;int n,m,p;
int a,b,c,d,x;
int tree[2050][2050][5];void in(int x,int y,int z)
{for(int i=x;i<=n;i+=lb(i))for(int j=y;j<=m;j+=lb(j)){tree[i][j][1]+=z;tree[i][j][2]+=z*x;tree[i][j][3]+=z*y;tree[i][j][4]+=z*x*y;}
}int fd(int x,int y)
{int s=0;for(int i=x;i;i-=lb(i))for(int j=y;j;j-=lb(j))s+=tree[i][j][1]*(x+1)*(y+1)-tree[i][j][2]*(y+1)-tree[i][j][3]*(x+1)+tree[i][j][4];return s;
}signed main()
{cin>>n>>m;while(scanf("%lld",&p)!=EOF){scanf("%lld%lld%lld%lld",&a,&b,&c,&d);if(p==1){scanf("%lld",&x);in(c+1,d+1,x);in(c+1,b,-x);in(a,d+1,-x);in(a,b,x);}elsecout<<fd(c,d)-fd(c,b-1)-fd(a-1,d)+fd(a-1,b-1)<<endl;}
}

这篇关于【ybt】【数据结构 树状数组 课过 例6】区间修改区间查询的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/658966

相关文章

从入门到精通MySQL联合查询

《从入门到精通MySQL联合查询》:本文主要介绍从入门到精通MySQL联合查询,本文通过实例代码给大家介绍的非常详细,需要的朋友可以参考下... 目录摘要1. 多表联合查询时mysql内部原理2. 内连接3. 外连接4. 自连接5. 子查询6. 合并查询7. 插入查询结果摘要前面我们学习了数据库设计时要满

MySQL查询JSON数组字段包含特定字符串的方法

《MySQL查询JSON数组字段包含特定字符串的方法》在MySQL数据库中,当某个字段存储的是JSON数组,需要查询数组中包含特定字符串的记录时传统的LIKE语句无法直接使用,下面小编就为大家介绍两种... 目录问题背景解决方案对比1. 精确匹配方案(推荐)2. 模糊匹配方案参数化查询示例使用场景建议性能优

关于集合与数组转换实现方法

《关于集合与数组转换实现方法》:本文主要介绍关于集合与数组转换实现方法,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录1、Arrays.asList()1.1、方法作用1.2、内部实现1.3、修改元素的影响1.4、注意事项2、list.toArray()2.1、方

mysql表操作与查询功能详解

《mysql表操作与查询功能详解》本文系统讲解MySQL表操作与查询,涵盖创建、修改、复制表语法,基本查询结构及WHERE、GROUPBY等子句,本文结合实例代码给大家介绍的非常详细,感兴趣的朋友跟随... 目录01.表的操作1.1表操作概览1.2创建表1.3修改表1.4复制表02.基本查询操作2.1 SE

MySQL数据库的内嵌函数和联合查询实例代码

《MySQL数据库的内嵌函数和联合查询实例代码》联合查询是一种将多个查询结果组合在一起的方法,通常使用UNION、UNIONALL、INTERSECT和EXCEPT关键字,下面:本文主要介绍MyS... 目录一.数据库的内嵌函数1.1聚合函数COUNT([DISTINCT] expr)SUM([DISTIN

XML重复查询一条Sql语句的解决方法

《XML重复查询一条Sql语句的解决方法》文章分析了XML重复查询与日志失效问题,指出因DTO缺少@Data注解导致日志无法格式化、空指针风险及参数穿透,进而引发性能灾难,解决方案为在Controll... 目录一、核心问题:从SQL重复执行到日志失效二、根因剖析:DTO断裂引发的级联故障三、解决方案:修复

mysql查询使用_rowid虚拟列的示例

《mysql查询使用_rowid虚拟列的示例》MySQL中,_rowid是InnoDB虚拟列,用于无主键表的行ID查询,若存在主键或唯一列,则指向其,否则使用隐藏ID(不稳定),推荐使用ROW_NUM... 目录1. 基本查询(适用于没有主键的表)2. 检查表是否支持 _rowid3. 注意事项4. 最佳实

SQL Server修改数据库名及物理数据文件名操作步骤

《SQLServer修改数据库名及物理数据文件名操作步骤》在SQLServer中重命名数据库是一个常见的操作,但需要确保用户具有足够的权限来执行此操作,:本文主要介绍SQLServer修改数据... 目录一、背景介绍二、操作步骤2.1 设置为单用户模式(断开连接)2.2 修改数据库名称2.3 查找逻辑文件名

MySQL存储过程之循环遍历查询的结果集详解

《MySQL存储过程之循环遍历查询的结果集详解》:本文主要介绍MySQL存储过程之循环遍历查询的结果集,具有很好的参考价值,希望对大家有所帮助,如有错误或未考虑完全的地方,望不吝赐教... 目录前言1. 表结构2. 存储过程3. 关于存储过程的SQL补充总结前言近来碰到这样一个问题:在生产上导入的数据发现

MySQL JSON 查询中的对象与数组技巧及查询示例

《MySQLJSON查询中的对象与数组技巧及查询示例》MySQL中JSON对象和JSON数组查询的详细介绍及带有WHERE条件的查询示例,本文给大家介绍的非常详细,mysqljson查询示例相关知... 目录jsON 对象查询1. JSON_CONTAINS2. JSON_EXTRACT3. JSON_TA