树状数组

xiaoxiao2021-02-28  22

问题引入:http://nyoj.top/problem/116

 

https://www.cnblogs.com/Howe-Young/p/4009223.html?ADUIN=1466989448&ADSESSION=1413411257&ADTAG=CLIENT.QQ.5359_.0&ADPUBNO=26397

 

树状数组详解: https://www.cnblogs.com/George1994/p/7710886.html

 

树状数组区间查询:https://blog.csdn.net/qq_21841245/article/details/43956633

 

树状数组lowbit讲解:https://www.cnblogs.com/circlegg/p/7189676.html

 

树状数组非常玄妙,核心在于lowbit,复杂度为log(n),二分的复杂度,树状数组也称二叉索引树。复杂度的期望值是比线段树低,代码比线段树简单很多,可是在解题范围上,线段树要比较大。

其中tem[x]代表的是原数组区间【x-lowbit(x)+1,x】的和。所以,查询区间【x-lowbit(x)+1,x】,a=x-lowbit(x).......【a-lowbit(a)+1,a】...(a>0)的和就是答案

lowbit()函数:函数用于找到最低位一的位置,其实树状数组的储存方法就是二进制,方法很玄妙。

#include<algorithm> #include<string.h> #include<stdio.h> using namespace std; int tem[1000000]; int n,m; int lowbit(int v) { return v&-v; } void add(int v,int e) { while(v<=n) { tem[v]+=e; v+=lowbit(v); } } int sum(int n) { int ans=0; while(n>0) { ans+=tem[n]; n-=lowbit(n); } return ans; } int main() { int l,r,x; char str[50]; scanf("%d%d",&n,&m); for(int i=1;i<=n;i++) { scanf("%d",&x); add(i,x); } while(m--) { scanf("%s%d%d",str,&l,&r); if(!strcmp(str,"QUERY")) { printf("%d\n",sum(r)-sum(l-1)); } else { add(l,r); } } }

 

转载请注明原文地址: https://www.6miu.com/read-2800166.html

最新回复(0)