【算法题】树状数组
建议点赞收藏关注！
本站友情链接：
- c/c++算法题指南
严书代码
c/c++大复习1
c/c++大复习2 - python算法题指南
牛客华为机试103精华
python输入输出大全
python语法
PAT甲级真题刷题笔记 共179道 - python官方文档
python官方文档 - 机试指南系列
基础篇
贪心篇
递归分治搜索篇
数据结构进阶篇（树/图/优先队列）
数学问题篇
动态规划篇
STL篇
目录
- 单点修改/查询
- 中点/最值查询
- 区间查询
树状数组：
可以区间求和、区间最大值、单点修改、快速求区间中点。一般不能区间修改（就这个结构而言）。
区间修改要用线段树。
非要用树状数组进行区间修改，则需要差分数组（也是单点修改、区间求和的数据结构）。
- lowbit(x)就是从右往左数，'1’所在的最低位
- 树状数组与lowbit的关系
树状数组利用lowbit存储前缀和。
例如：idx=[0,1…8]
0:这里忽略，只占位, index(0)=0
1: 01 -> lowbit=1
2: 10-> lowbit=2
3: 11 -> lowbit=1
4: 100-> lowbit=3
5: 101-> lowbit=1
6: 110-> lowbit=2
7: 111-> lowbit=1
8: 1000-> lowbit=4
lowbit=1的有1，3，5，7
lowbit=2的有2，6
lowbit=3的有4
lowbit=4的有8
则得到如下图像
sum of（又称前缀和） 的范围计算为tree[i] = sum(a[i - lowbit(i) + 1],…,a[i])
lowbit可以表示区间的长度.也可以作为指针查询对应的某个tree
如果要求【图1】中下标1~3的和，则：
设ans=0, x=3
ans+=a[3] #a[3]=3 ans更新为3
x-=lowbit(3) #往前走，x更新为2
#x不为0，继续
ans+=a[2] #a[2]=3 ans更新为6
x-=lowbit(2)
#x为0，停止，此时ans=6
- 题型
#模版
def lowbit(x):return x & (-x)# 1、树状数组前缀和
# 求前缀和a[i] + ... + a[x]
# 从x出发，往左走，每次减去lowbit(x)
def query(x, tree):""":param x:前x项的前缀和:param tree:树状数组:return:ans 前x项的前缀和"""ans = 0while x:ans += tree[x]x -= lowbit(x)return ans# 实现单点的更新
# 如果将a[x] + y?
# 从x出发向右走，每次加上lowbit(x),所以经过的点都加上y
def add(x, y, tree, n):while x <= n:tree[x] += yx += lowbit(x)n = int(input())
a = [0] + list(map(int, input().split()))#0占位tree = [0] * (n + 1)
# 初始化的过程构造树状数组
for i in range(1, n + 1):add(i, a[i], tree, n)m = int(input())
for _ in range(m):op, a, b = map(int, input().split())if op == 1:add(a, b, tree, n)else: #[a,b]的元素和print(query(b, tree) - query(a - 1, tree))单点修改/查询
指定某一个格子x，令x 进行操作：加上或者减去一个特定的值A。
for i in range(m):op = list(map(int, input().split()))if op[0] == 1:#单点修改x, y = op[1], op[2]add(x, y - a[x])#新旧两者的差值a[x] = y # 不要忘记这一步else:#单点查询x = op[1]print(a[x])
中点/最值查询
在一个升序数组中，前缀出现次数 >= 数组大小+1的一半的第一个元素，即为中间值。
将入栈元素作为数组下标（类似于桶排序），将其出现次数存入一个数组中，然后求前缀出现次数.
查询[L,R]范围的最大值：
从右往左开始查询,len表示[L,R]的长度,len=R-L+1.当使用tree[x]=[x-lowbit(x)+1,x]之间的最大值,lowbit(x)可以表示区间长度,
如果len>= lowbit（R）,那么tree[R]可以直接取出来比较ans=max(ans,tree[R]).
例如求[4,7]之间的最大值,len=4,lowbit(7)=1，(tree[7]=arr[7]).
如果lowbit（R）>len呢,直接拿arr[R]来比较就行了,ans=max(ans,arr[R]).
1057 Stack 查询中值
用python会有两个测试点超时，这个确实无解，只能用c++写
s = list()
c = [0 for i in range(100861)]#树状数组 题目范围不超过10^5def lowBit(x):return x & (-x)def update(x, v):i = xwhile i < 100861:c[i] += vi += lowBit(i)def getSum(x):sum, i = 0, x #sum=0 ,i=xwhile i >= 1:sum += c[i]i -= lowBit(i)return sumdef find():left, right, k = 1, 100861, (len(s) + 1) // 2while left < right:mid = (left + right) // 2if getSum(mid) >= k:right = midelse:left = mid + 1print(left)def solve():global c, sn = int(input())for i in range(n):command = input().split()if command[0][1] == 'u':#pushs.append(int(command[1]))update(int(command[1]), 1)elif command[0][1] == 'o':#popif len(s) == 0:print("Invalid")else:update(s[-1], -1)print(s[-1])s.pop()elif command[0][1] == 'e':#medianif len(s) == 0:print("Invalid")else:find()if __name__ == "__main__":solve()#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<vector>
#include<queue>
#include<stack>
#include<cstring>
#include<string>
#include<cmath>#define inf 0xffffffff
#define lowbit(i) ((i)&(-(i)))
using namespace std;const int maxn=100861;stack<int> s;
int c[maxn];void update(int x, int v)
{for(int i=x; i<maxn; i+=lowbit(i))c[i]+=v;
}int sum(int x)
{int t=0;for(int i=x; i>=1; i-=lowbit(i))t+=c[i];return t;
}void find()
{int left=0;int right=maxn;int mid;int k=(s.size()+1)>>1;//size_midwhile(left<right){mid=(left+right)>>1;if(sum(mid)>=k)right=mid;elseleft=mid+1;}printf("%d\n", left);
}int main()
{int n;scanf("%d", &n);char command[15];for(int i=0; i<n; i++){scanf("%s", command);if(command[1]=='u')//push{int t;scanf("%d", &t);update(t, 1);s.push(t);}elseif(command[1]=='o')//popif(s.size()==0)printf("Invalid\n");else{update(s.top(), -1);printf("%d\n", s.top());s.pop();}elseif(command[1]=='e')//medianif(s.size()==0)printf("Invalid\n");elsefind();}return 0;
}区间查询
查询某一个特定的子区间[a, b]中所有元素的元素和。
print(query(b, tree) - query(a - 1, tree))