首页 > 其他分享 >树状数组

树状数组

时间:2024-08-30 16:47:27浏览次数:12  
标签:树状 二进制 lowbit 复杂度 数组 logn

树状数组用于变化区间的动态维护进行 \(O(logn)\) 的插入和删除。

\(lowbit(x)\) 表示二进制表示中最低位的1代表的值称为最小位值,实际上就是二进制表示中最低位的1代表的值称为最小位值 二进制表示中最低位的1加上后面的0的值。

设树状数组\(c\), \(c_i\) 表示 ${\textstyle \sum_{i = i - lowbit(i) + 1}^{i}c[i]} $,每次修改操作只需要修改包含 \(i\) 的c, 复杂度为 \(O(logn)\)。每次查询操作,将分段拼起来,复杂度为 \(O(logn)\)。


void init() {
	for (int i = 1; i <= n; i++) {
 	   c[i] = a[i];
 	}
}

int lowbit(int x) { 
  return x & -x;
}

void add(int x, int y) {
  for (int i = x; i <= n; i += lowbit(i)) {
    c[i] += y;
  }
}

int sum(int x) {
  int ans = 0;
  for (int i = x; i > 0; i -= lowbit(i)) {
    ans += c[i];
  }
  return ans;
}

当需要区间修改时,就需要差分了。

\(c\) 不再需要初始值,最后加上就行。

add(u, k), add(v + 1, -k);

cout << a[u] + sum(u) << '\n';

标签:树状,二进制,lowbit,复杂度,数组,logn
From: https://www.cnblogs.com/JiCanDuck/p/18389050

相关文章

  • 两个集合对都包含id,且id相同的数组进行过滤;返回需求集合
    ResponseEntity<Page<WmsInventoryHistoryVO>>ok=ResponseEntity.ok(service.selectList(newWmsInventoryHistory(),page));WmsInventoryHistorywmsInventoryHistory=newWmsInventoryHistory();wmsInventoryHistory.setWarehouseId(i......
  • 【3.4】贪心算法-解按要求补齐数组
    一、问题        给定一个已排序的正整数数组nums,和一个正整数n。从[1,n]区间内选取任意个数字补充到nums中,使得[1,n]区间内的任何数字都可以用nums中某几个数字的和来表示。请输出满足上述要求的最少需要补充的数字个数。......
  • 数组学习
    可变参数◆JDK1.5开始,Java支持传递同类型的可变参数给一个方法。◆在方法声明中,在指定参数类型后加一个省略号(...)。◆一个方法中只能指定一个可变参数,它必须是方法的最后一个参数。任何普通的参数必须在它之前声明。packagecom.yanna.method;publicclassDemo04......
  • 01-数组
    1.理论基础数组是存放在连续内存空间上的相同类型数据的集合。数组可以方便的通过下标索引的方式获取到下标下对应的数据。数组的简单示例:数组内存空间的地址是连续的正是因为数组的在内存空间的地址是连续的,所以我们在删除或者增添元素的时候,就难免要移动其他元素的地址。......
  • ES6两个数组进行比较
    在ES6中,可以使用扩展运算符...和Array.prototype.includes方法来比较两个数组,并找出它们的不同元素。constarray1=[1,2,3,4,5];constarray2=[3,4,5,6,7];//找出在array1中而不在array2中的元素constdiff1=array1.filter(item=>!array2.includes(item));//......
  • C语言详细笔记--构造数据类型(结构体数组)
    目录一、结构体数组的定义二、结构体数组的初始化三、结构体数组的引用一、结构体数组的定义structstuscoretype{intstuid;intscore[3];doubleaverage;};structstuscoretypestu[3];上面语句定义了一个名为stu的数组,数组有三个元素,每个元素的类......
  • 力扣238.除自身以外数组的乘积
    classSolution{publicint[]productExceptSelf(int[]nums){//获取数组长度intlength=nums.length;//创建一个新数组,用于存储结果int[]answer=newint[length];//初始化第一个元素为1,因为乘积不包括自身......
  • 仅利用一维数组实现等值线图效果(附完整代码)
    当我们有三个一维数组x,y,i,其中i表示强度(或者其它),用颜色深浅表示。现在我们需要实现以下需求:使用一维数组x、y、i,其中i用于表示颜色深浅。在三维坐标系中,图像位于指定的z轴位置(如z=230)。生成的图像效果类似二维等值线图(ContourPlot)。 那么效果类似怎样的呢?如下图所示......
  • 代码随想录算法训练营,29日 | 704. 二分查找,27. 移除元素,977.有序数组的平方,209.长度最
    数组基础文档讲解︰代码随想录(programmercarl.com)1.连续空间、相同类型元素2.元素只能覆盖3.二维数组的地址连续吗(C++连续,Java不连续)704.二分查找题目链接:704.二分查找文档讲解︰代码随想录(programmercarl.com)视频讲解︰二分查找日期:2024-08-29思路:第一反应是想到二分查......
  • 求数组的最大值-Day2
    求数组[12,1,2,3000,130,31,12,200,500]最大值:声明并保存一个最大元素的变量max默认max取数组第一个元素遍历数组,将每个元素与max做大小比较如果该元素大于max,将这个元素存到max里,否则下一轮最后输出maxletarr=[12,1,2,3000,130,31,12,200,500]l......