树状数组原理

简介: 笔记

功能:


①快速求前缀和O ( l o g n )

②修改某一个数O ( l o g n )

7.png


操作:


①:建树

void add(int x, int c) { //树状数组的插入操作
  for (int i = x;i <= n;i += lowbit(i))tr[i] += c;
}

②:区间查询:1 ~ x 前缀和

for(int i = x;i <= n;i += lowbit(i))res += c;


③:单点修改:

for(int i = x;i;i -= lowbit(i))tr[i] += c;


目录
相关文章
|
1月前
|
算法 Java 索引
数据结构与算法学习十五:常用查找算法介绍,线性排序、二分查找(折半查找)算法、差值查找算法、斐波那契(黄金分割法)查找算法
四种常用的查找算法:顺序查找、二分查找(折半查找)、插值查找和斐波那契查找,并提供了Java语言的实现代码和测试结果。
20 0
|
6月前
|
搜索推荐 C++
快速排序算法的原理与实现
快速排序算法的原理与实现
52 3
|
11月前
|
搜索推荐 算法 C语言
手撕排序算法3:优化版冒泡排序和快速排序的三种方法(包括三数取中,小区间优化,递归版本)(上)
手撕排序算法3:优化版冒泡排序和快速排序的三种方法(包括三数取中,小区间优化,递归版本)(上)
手撕排序算法3:优化版冒泡排序和快速排序的三种方法(包括三数取中,小区间优化,递归版本)(上)
|
6月前
|
存储 搜索推荐 索引
快速排序算法和原理
快速排序算法和原理
|
11月前
|
搜索推荐 算法
手撕排序算法3:优化版冒泡排序和快速排序的三种方法(包括三数取中,小区间优化,递归版本)(下)
手撕排序算法3:优化版冒泡排序和快速排序的三种方法(包括三数取中,小区间优化,递归版本)(下)
|
机器学习/深度学习 存储 算法
【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)
【数据结构与算法篇】手撕八大排序算法之快排的非递归实现及递归版本优化(三路划分)
205 0
|
存储 人工智能
|
算法
一道线段树相关算法题
每个方块都从一个比目前所有的落地方块更高的高度掉落而下。方块沿 y 轴负方向下落,直到着陆到 另一个正方形的顶边 或者是 x 轴上 。一个方块仅仅是擦过另一个方块的左侧边或右侧边不算着陆。一旦着陆,它就会固定在原地,无法移动。
104 0
一道线段树相关算法题
(树状数组,线段树)(数组模拟哈希)(解题步骤)acwing数星星
(树状数组,线段树)(数组模拟哈希)(解题步骤)acwing数星星
94 0
|
算法 搜索推荐
算法笔记(二)——快排,归并算法(做成模板题)
算法笔记(二)——快排,归并算法(做成模板题)
算法笔记(二)——快排,归并算法(做成模板题)