poj 3486 A Simple Problem with Integers(树状数组第三种模板改段求段)
2023-09-27 14:20:24 时间
1 /* 2 树状数组第三种模板(改段求段)不解释!
不明白的点这里:here! 3 */ 4 #include<iostream> 5 #include<cstring> 6 #include<cstdio> 7 #include<algorithm> 8 #define N 100005 9 using namespace std; 10 11 typedef long long LL; 12 13 LL ss[N], B[N], C[N]; 14 15 int n, m; 16 17 void addB(int x, int k){//B[i]表示被1...i整体一共加了多少的总和 18 for(int i=x; i<=n; i+=i&(-i)) B[i]+=x*k; 19 } 20 21 void addC(int x, int k){//1....x节点的每个节点的增量 22 for(int i=x; i>0; i-=i&(-i)) C[i]+=k; 23 } 24 25 LL sumB(int x){ 26 LL s=0; 27 for(int i=x; i>0; i-=i&(-i)) s+=B[i]; 28 return s; 29 } 30 31 LL sumC(int x){//x节点总共的增量 32 LL s=0; 33 for(int i=x; i<=n; i+=i&(-i)) s+=C[i]; 34 return s; 35 } 36 37 LL sum(int x){ 38 return x==0 ? 0 : sumC(x)*x + sumB(x-1); 39 } 40 41 void update(int a, int b, int c){ 42 addB(b, c); 43 addC(b, c); 44 if(a-1>0){ 45 addB(a-1, -c); 46 addC(a-1, -c); 47 } 48 } 49 50 int main(){ 51 int m; 52 while(scanf("%d%d", &n, &m)!=EOF){ 53 for(int i=1; i<=n; ++i){ 54 scanf("%lld", &ss[i]); 55 ss[i]+=ss[i-1]; 56 } 57 char ch[2]; 58 int a, b, c; 59 while(m--){ 60 scanf("%s", ch); 61 if(ch[0]=='Q'){ 62 scanf("%d%d", &a, &b); 63 printf("%lld\n", ss[b]-ss[a-1]+sum(b)-sum(a-1)); 64 } 65 else{ 66 scanf("%d%d%d", &a, &b, &c); 67 update(a, b, c); 68 } 69 } 70 } 71 return 0; 72 }
相关文章
- POJ2446 模板盖格子 简单二分匹配
- Java描述设计模式(19):模板方法模式
- 14 vue的data函数中对象和数组的方式绑定模板样式
- js模板引擎
- 【Excel】+添加模板
- SpringBoot视图模板库
- Vue+Echarts监控大屏实例二:促销活动监控模板实例
- 个人常用的 matplotlib 绘图模板
- 408 | 数据结构代码算法题模板技巧 之 顺序表(数组)
- 洛谷 P3384 【模板】树链剖分
- Laravel 4 Blade模板引擎
- asp.net MVC提高开发速度(创建项目模板)
- Python 框架 之 Django MVT 下的 T 的 模板简单介绍和使用
- 求逆序数模板(树状数组+离散化 || 归并排序法)
- Thymeleaf常用语法:模板片断
- metronic后台模板学习 -- 所用外部插件列表
- Spring Boot 2.X 使用 Thymeleaf 模板引擎