当前位置: 首页 > news >正文

两种树状数组

单点修改,区间查询树状数组,洛谷P3374

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, a[N];
int chaxun(int n){int ans = 0;while(1){ans += a[n];int x = n & -n;n -= x;if(n == 0) break;}return ans;
}
void xiugai(int n, int d){while(1){a[n] += d;int x = n & -n;n += x;if(n >= N) break;}return;
}
int main(){int f, x, y;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> x;xiugai(i,x);	}while(m--){cin >> f >> x >> y;if(f == 1) xiugai(x, y);if(f == 2){cout << chaxun(y) - chaxun(x-1) << endl;}}return 0;
}

区间修改,单点查询树状数组,洛谷P3368

把上面那个改成在原数组差分数组上做

#include<bits/stdc++.h>
using namespace std;
const int N = 5e5 + 5;
int n, m, s[N], a[N];
int chaxun(int n){int ans = 0;while(1){ans += s[n];int x = n & -n;n -= x;if(n == 0) break;}return ans;
}
void xiugai(int n, int d){while(1){s[n] += d;int x = n & -n;n += x;if(n >= N) break;}return;
}
int main(){int f, x, y, k;cin >> n >> m;for(int i = 1; i <= n; i++){cin >> a[i];x = a[i] - a[i-1];xiugai(i,x);	}while(m--){cin >> f;if(f == 1){cin >> x >> y >> k;xiugai(x,k);xiugai(y+1,-k);}if(f == 2){cin >> x;cout << chaxun(x) << endl;}}return 0;
}
http://www.hskmm.com/?act=detail&tid=33324

相关文章:

  • 斑马日记2025.10.17
  • CF Global Round 29(#2147) 总结
  • 详细介绍:C语言中#pragma的用法
  • JAVA 中断处理
  • 第十五天
  • 软件工程学习日志2025.10.17
  • 天黑了,睡觉
  • 升鲜宝生鲜配送供应链管理系统---- 门店收银 POS 离线工作设计文档(支持线上线下一体化)---02
  • 2025.10.16NOIP模拟
  • Python 基于Python开发的数据库同步检测工具
  • 当AI学会进化:荣耀与用户的“共生式成长”新范式
  • VSCode的下载安装以及配置
  • 2025年终极公众号排版神器排行榜 最新案例研究权威测评
  • NAS安装远程协作神器twake
  • 把三门问题做成了"游戏"
  • 下一代CPU驱动高性能计算革新
  • [KaibaMath]1010 关于关于收敛数列有界性的证明
  • 卫星地图匹配定位 - MKT
  • 10.17 —— (VP) 2021icpc沈阳
  • 10.17每日总结
  • 今天宝宝进面了
  • 《大象Thinking in Projects》读书笔记1
  • 20251017
  • MT签名去除签名校验分析
  • uml
  • P3643 [APIO2016] 划艇 分析
  • day016
  • uml九图和数据流图总结
  • UpdateSourceTrigger和Mode的区别
  • NOIP2020 T2