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

相关文章

csu 1446 Problem J Modified LCS (扩展欧几里得算法的简单应用)

这是一道扩展欧几里得算法的简单应用题,这题是在湖南多校训练赛中队友ac的一道题,在比赛之后请教了队友,然后自己把它a掉 这也是自己独自做扩展欧几里得算法的题目 题意:把题意转变下就变成了:求d1*x - d2*y = f2 - f1的解,很明显用exgcd来解 下面介绍一下exgcd的一些知识点:求ax + by = c的解 一、首先求ax + by = gcd(a,b)的解 这个

hdu2241(二分+合并数组)

题意:判断是否存在a+b+c = x,a,b,c分别属于集合A,B,C 如果用暴力会超时,所以这里用到了数组合并,将b,c数组合并成d,d数组存的是b,c数组元素的和,然后对d数组进行二分就可以了 代码如下(附注释): #include<iostream>#include<algorithm>#include<cstring>#include<stack>#include<que

活用c4d官方开发文档查询代码

当你问AI助手比如豆包,如何用python禁止掉xpresso标签时候,它会提示到 这时候要用到两个东西。https://developers.maxon.net/论坛搜索和开发文档 比如这里我就在官方找到正确的id描述 然后我就把参数标签换过来

poj 3974 and hdu 3068 最长回文串的O(n)解法(Manacher算法)

求一段字符串中的最长回文串。 因为数据量比较大,用原来的O(n^2)会爆。 小白上的O(n^2)解法代码:TLE啦~ #include<stdio.h>#include<string.h>const int Maxn = 1000000;char s[Maxn];int main(){char e[] = {"END"};while(scanf("%s", s) != EO

hdu 2602 and poj 3624(01背包)

01背包的模板题。 hdu2602代码: #include<stdio.h>#include<string.h>const int MaxN = 1001;int max(int a, int b){return a > b ? a : b;}int w[MaxN];int v[MaxN];int dp[MaxN];int main(){int T;int N, V;s

poj 1511 Invitation Cards(spfa最短路)

题意是给你点与点之间的距离,求来回到点1的最短路中的边权和。 因为边很大,不能用原来的dijkstra什么的,所以用spfa来做。并且注意要用long long int 来存储。 稍微改了一下学长的模板。 stack stl 实现代码: #include<stdio.h>#include<stack>using namespace std;const int M

poj 3259 uva 558 Wormholes(bellman最短路负权回路判断)

poj 3259: 题意:John的农场里n块地,m条路连接两块地,w个虫洞,虫洞是一条单向路,不但会把你传送到目的地,而且时间会倒退Ts。 任务是求你会不会在从某块地出发后又回来,看到了离开之前的自己。 判断树中是否存在负权回路就ok了。 bellman代码: #include<stdio.h>const int MaxN = 501;//农场数const int

poj 1258 Agri-Net(最小生成树模板代码)

感觉用这题来当模板更适合。 题意就是给你邻接矩阵求最小生成树啦。~ prim代码:效率很高。172k...0ms。 #include<stdio.h>#include<algorithm>using namespace std;const int MaxN = 101;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int n

poj 1287 Networking(prim or kruscal最小生成树)

题意给你点与点间距离,求最小生成树。 注意点是,两点之间可能有不同的路,输入的时候选择最小的,和之前有道最短路WA的题目类似。 prim代码: #include<stdio.h>const int MaxN = 51;const int INF = 0x3f3f3f3f;int g[MaxN][MaxN];int P;int prim(){bool vis[MaxN];

poj 2349 Arctic Network uva 10369(prim or kruscal最小生成树)

题目很麻烦,因为不熟悉最小生成树的算法调试了好久。 感觉网上的题目解释都没说得很清楚,不适合新手。自己写一个。 题意:给你点的坐标,然后两点间可以有两种方式来通信:第一种是卫星通信,第二种是无线电通信。 卫星通信:任何两个有卫星频道的点间都可以直接建立连接,与点间的距离无关; 无线电通信:两个点之间的距离不能超过D,无线电收发器的功率越大,D越大,越昂贵。 计算无线电收发器D