POJ 3468 A Simple Problem with Integers 树状数组 区间修改 区间查询

2024-08-24 12:18

本文主要是介绍POJ 3468 A Simple Problem with Integers 树状数组 区间修改 区间查询,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

题目链接点这儿

给你一个数列,最多10W次操作,要么区间统一加上某个值,要么查询某个区间的和。


第一反应肯定是线段树,但是呢,这个能不能用树状数组做呢?

如果是单点修改,区间查询,我们直接在原数列上进行树状数组的操作。


如果是区间修改,单点查询。由于树状数组每次update一个单点x之后,会对n>x的getsum(n)(或者说树状数组的Query(n)操作)都有影响。也就是说,虽然修改的是单点,但对查询的影响是区间的。从而我们可以利用这个,在保持原数列不改变的同时另找一个树状数组来记录每个位置修改的值。如果在区间[i, j]每个值增加delta,那么我们可以通过update(i, delta), update(j+1, -delta)的操作来使getsum(pos)的值就是pos这个位置到这一时刻位置为止的改变量。从而查询i处的值的话,只需返回a[i] + getsum(i)(a[i]是该位置的初始值)。


那么现在要区间查询,仍然可以借助区间修改,单点查询的思路,但是我们还要求Σgetsum(i)(i >= left value, i <= right value),这个操作直接写明显会浪费很大力气。

我们记树状数组维护的那个数组为b[](也就是说这个数组满足为点k处的修改值)

我们现在要求的是经过转换后有,那么在转换一下的话,我们就有了。那么到了这一步之后,我们可以发现,前两项都是一个树状数组的Query操作,而最后一项也可以表示成另一个树状数组i*bi的两次Query操作之差。从而我们找到了用树状数组模拟线段树区间操作的方法。

下面放出代码

[cpp]  view plain copy print ? 在CODE上查看代码片 派生到我的代码片
  1. #include <vector>  
  2. #include <list>  
  3. #include <map>  
  4. #include <set>  
  5. #include <deque>  
  6. #include <queue>  
  7. #include <stack>  
  8. #include <bitset>  
  9. #include <algorithm>  
  10. #include <functional>  
  11. #include <numeric>  
  12. #include <utility>  
  13. #include <sstream>  
  14. #include <iostream>  
  15. #include <iomanip>  
  16. #include <cstdio>  
  17. #include <cmath>  
  18. #include <cstdlib>  
  19. #include <cctype>  
  20. #include <string>  
  21. #include <cstring>  
  22. #include <cstdio>  
  23. #include <cmath>  
  24. #include <cstdlib>  
  25. #include <ctime>  
  26. #include <climits>  
  27.   
  28. #define up(i, lower, upper) for(int i = lower; i < upper; i++)  
  29. #define down(i, lower, upper) for(int i = upper-1; i >= lower; i--)  
  30.   
  31. using namespace std;  
  32.   
  33. #define MAX_N 100010  
  34. typedef pair<intint> pii;  
  35. typedef pair<doubledouble> pdd;  
  36. typedef vector<int> vi;  
  37. typedef vector<pii> vpii;  
  38. typedef long long ll;  
  39. typedef unsigned long long ull;  
  40.   
  41. const double pi = acos(-1.0);  
  42. const double eps = 1.0e-9;  
  43.   
  44. template<class T>  
  45.   
  46. inline bool read(T &n){  
  47.     T x = 0, tmp = 1; char c = getchar();  
  48.     while((c < '0' || c > '9') && c != '-' && c != EOF) c = getchar();  
  49.     if(c == EOF) return false;  
  50.     if(c == '-') c = getchar(), tmp = -1;  
  51.     while(c >= '0' && c <= '9') x *= 10, x += (c - '0'),c = getchar();  
  52.     n = x*tmp;  
  53.     return true;  
  54. }  
  55.   
  56. template <class T>  
  57. inline void write(T n) {  
  58.     if(n < 0) {  
  59.         putchar('-');  
  60.         n = -n;  
  61.     }  
  62.     int len = 0,data[20];  
  63.     while(n) {  
  64.         data[len++] = n%10;  
  65.         n /= 10;  
  66.     }  
  67.     if(!len) data[len++] = 0;  
  68.     while(len--) putchar(data[len]+48);  
  69. }  
  70.   
  71. struct BIT {  
  72.     ll sum[MAX_N];  
  73.     int len;  
  74.   
  75.     BIT() {  
  76.         len = 0;  
  77.         memset(sum, 0, sizeof sum);  
  78.     }  
  79.   
  80.     BIT(int len) : len(len) {  
  81.         memset(sum, 0, sizeof sum);  
  82.     }  
  83.   
  84.     ll lowbit(ll x) { return x&(-x); }  
  85.   
  86.     ll getsum(int n) {  
  87.         ll ans = 0;  
  88.         while(n > 0) ans+=sum[n], n-=lowbit(n);  
  89.         return ans;  
  90.     }  
  91.   
  92.     void update(int pos, ll val) {  
  93.         while(pos <= len) sum[pos] += val, pos+=lowbit(pos);  
  94.     }  
  95. };  
  96. //-------------------------------------------------------  
  97.   
  98. BIT a, b;  
  99.   
  100. int main() {  
  101.     int n, m, l, r, val;  
  102.     ll sum[100010] = { 0 };  
  103.     char str[2];  
  104.     read(n), read(m);  
  105.     a.len = b.len = n;  
  106.     up(i, 1, n+1) read(val), sum[i] = sum[i-1] + val;  
  107.     up(i, 0, m) {  
  108.         scanf("%s", str);  
  109.         if(str[0] == 'C') {  
  110.             read(l), read(r), read(val);  
  111.             a.update(l, val), a.update(r+1, -val);  
  112.             b.update(l, val*l), b.update(r+1, -val*(r+1));  
  113.         }  
  114.         else {  
  115.             read(l), read(r);  
  116.             //printf("%lld", sum[r] - sum[l-1] + a.getsum(r)*(r+1) - a.getsum(l-1)*l - b.getsum(r) + b.getsum(l-1));  
  117.             write(sum[r] - sum[l-1] + a.getsum(r)*(r+1) - a.getsum(l-1)*l - b.getsum(r) + b.getsum(l-1));  
  118.             puts("");  
  119.         }  
  120.     }  
  121.     return 0;  
  122. }  

这篇关于POJ 3468 A Simple Problem with Integers 树状数组 区间修改 区间查询的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



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

相关文章

MyBatis-Plus通用中等、大量数据分批查询和处理方法

《MyBatis-Plus通用中等、大量数据分批查询和处理方法》文章介绍MyBatis-Plus分页查询处理,通过函数式接口与Lambda表达式实现通用逻辑,方法抽象但功能强大,建议扩展分批处理及流式... 目录函数式接口获取分页数据接口数据处理接口通用逻辑工具类使用方法简单查询自定义查询方法总结函数式接口

MySql基本查询之表的增删查改+聚合函数案例详解

《MySql基本查询之表的增删查改+聚合函数案例详解》本文详解SQL的CURD操作INSERT用于数据插入(单行/多行及冲突处理),SELECT实现数据检索(列选择、条件过滤、排序分页),UPDATE... 目录一、Create1.1 单行数据 + 全列插入1.2 多行数据 + 指定列插入1.3 插入否则更

MySQL 多列 IN 查询之语法、性能与实战技巧(最新整理)

《MySQL多列IN查询之语法、性能与实战技巧(最新整理)》本文详解MySQL多列IN查询,对比传统OR写法,强调其简洁高效,适合批量匹配复合键,通过联合索引、分批次优化提升性能,兼容多种数据库... 目录一、基础语法:多列 IN 的两种写法1. 直接值列表2. 子查询二、对比传统 OR 的写法三、性能分析

Java中的数组与集合基本用法详解

《Java中的数组与集合基本用法详解》本文介绍了Java数组和集合框架的基础知识,数组部分涵盖了一维、二维及多维数组的声明、初始化、访问与遍历方法,以及Arrays类的常用操作,对Java数组与集合相... 目录一、Java数组基础1.1 数组结构概述1.2 一维数组1.2.1 声明与初始化1.2.2 访问

从入门到精通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断裂引发的级联故障三、解决方案:修复