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

【算法】树状数组维护总结

本文仅对树状数组的使用作一个总结,并非讲解。

这里的操作都对长度为 n n n 的数组 a a a 进行操作。

单点修改,区间查询

  • 暴力做法:

    • 修改: a [ x ] = y a[x]=y a[x]=y,时间复杂度为 O ( 1 ) O(1) O(1)
    • 查询: ∑ i = l r a [ i ] \sum\limits_{i=l}^ra[i] i=lra[i] ,时间复杂度为 O ( n ) O(n) O(n)
  • 树状数组:
    t r tr tr 数组 对 a a a 数组进行维护

    • 修改:

      void update(int x, int y) {
      	while (x <= n) tr[x] += y, x += (x & (-x));
      }
      
      update(x, y);
      

      时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)

    • 查询:

      int query(int x) {
      	int ans = 0;
      	while (x >= 1) ans += tr[x], x -= (x & (-x));
      	return ans;
      }
      

      时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)

区间修改,单点查询

  • 暴力做法:

    • 修改: a [ l ] = a [ l ] + x , ⋯   , a [ r ] = a [ r ] + x a[l]=a[l]+x,\cdots,a[r]=a[r]+x a[l]=a[l]+x,,a[r]=a[r]+x,时间复杂度为 O ( n ) O(n) O(n)
    • 查询: a [ x ] a[x] a[x],时间复杂度为 O ( 1 ) O(1) O(1)
  • 树状数组:
    b b b 数组是 a a a 的差分数组。 t r tr tr 数组对 b b b 数组进行维护

    • 修改:
      void update(int x, int y) {
      	while (x <= n) tr[x] += y, x += (x & (-x));
      }
      
      update(l, x);
      update(r + 1, -x);
      
      时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)
    • 查询:
      int query(int x) {
      	int ans = 0;
      	while (x >= 1) ans += tr[x], x -= (x & (-x));
      	return ans;
      }
      
      query(x);
      
      时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)

区间修改,区间查询

区间查询的的公式为: ∑ i = l r a [ i ] \sum\limits_{i=l}^ra[i] i=lra[i],我们先考虑如何求 ∑ i = 1 p a [ i ] \sum\limits_{i=1}^p a[i] i=1pa[i]

问题转换为如何去求解这个公式,暴力情况下,求 a [ i ] a[i] a[i] O ( log ⁡ n ) O(\log n) O(logn),总时间复杂度为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

但是我们可以拆分这个公式:
∑ i = 1 p a [ i ] = ∑ i = 1 p ∑ j = 1 i b [ j ] = p × b [ 1 ] + ( p − 1 ) × b [ 2 ] + ⋯ + 1 × b [ p ] = ( ( p + 1 ) × ∑ i = 1 p b [ i ] ) − ( 1 × b [ 1 ] + 2 × b [ 2 ] + ⋯ + p × b [ p ] ) \begin{aligned} \sum\limits_{i=1}^p a[i] &=\sum\limits_{i=1}^p \sum\limits_{j=1}^ib[j] \\ &= p \times b[1]+(p-1)\times b[2]+\cdots+1\times b[p] \\ &= ((p+1)\times \sum\limits_{i=1}^p b[i])-(1\times b[1]+2\times b[2]+\cdots+p\times b[p])\\ \end{aligned} i=1pa[i]=i=1pj=1ib[j]=p×b[1]+(p1)×b[2]++1×b[p]=((p+1)×i=1pb[i])(1×b[1]+2×b[2]++p×b[p])

所以我们再用一个额外的树状数组去维护 i × b [ i ] i\times b[i] i×b[i] 即可。

// 区间修改[x, n]
const int N =100010;
int tr1[N], tr2[N];
void update(int x, int y) {
	int val2 = x * y;
	while (x <= n) {
		tr1[x] += y;
		tr2[x] += val2;
		x += (x & (-x));
	}
}
update(l, d);      // a[l, n] += d;
update(r + 1, -d); // a[r + 1, n] -= d

// 区间查询(1, x)
int query(int x) {
	int p = x;
	int val1 = 0, val2 = 0;
	while (x >= 1) {
		val1 += tr1[x];
		val2 += tr2[x];
		x -= (x & -x);
	}
	return (p + 1) * val1 - val2;
}
// 查询 a[l, r]
query(1, r) - query(1, l - 1);

时间复杂度为 O ( log ⁡ n ) O(\log n) O(logn)


http://www.kler.cn/a/6508.html

相关文章:

  • 前端使用 Konva 实现可视化设计器(20)- 性能优化、UI 美化
  • leetcode之hot100---234回文链表(C++)
  • jvm栈帧中的动态链接
  • OpenCV putText增加中文支持
  • 20241217使用M6000显卡在WIN10下跑whisper来识别中英文字幕
  • Word使用分隔符实现页面部分分栏
  • 计算机底层:循环冗余校验码CRC
  • 实验十八、测量运放的开环差模放大倍数
  • 实验二 配置Trunk和链路汇聚
  • 近世代数 笔记与题型连载 第八章(置换群)
  • Linux之进程替换
  • Octree(八叉树)
  • 【进阶C语言】指针和数组笔试题解析
  • 愚人节,聊聊那些正在坑人的“新型AI”
  • 实验5 数字图像基础
  • python函数
  • 【Python入门第四十六天】Python丨NumPy 数组重塑
  • 关于分布式系统缓存扩容的一些总结(面试装逼能用实际也很有用)
  • 【机器学习算法实践】GBDT提升树,集成学习boosting方法,可分类课可回归,CART树是基础,调参是重点
  • 第十四届CCPC吉林省赛题解
  • 20230405英语学习
  • 溯源取证-钓鱼取证 基础篇
  • NDK RTMP直播客户端一
  • Android事件分发机制小结
  • 看ChatGPT如何回答微博签到数据相关问题。
  • Linux-