中小企业的网站建设,安徽安庆地图,推广app文案,棋牌源码搭建论坛树状数组的作用#xff1a;快速的对数列的一段范围求和快速的修改数列的某一个数为什么要使用树状数组#xff1a;大家从作用中看到快速求和的时候可能会想到为什么不使用前缀和只需要预处理一下就可以在O(1)的时间复杂度下实行对于数列的一段范围的和但是我们可以得到当我们…树状数组的作用快速的对数列的一段范围求和快速的修改数列的某一个数为什么要使用树状数组大家从作用中看到快速求和的时候可能会想到为什么不使用前缀和只需要预处理一下就可以在O(1)的时间复杂度下实行对于数列的一段范围的和但是我们可以得到当我们需要进行功能不仅含有范围求和还要求在同时对于数列的某个数进行修改的时候我们每次修改后还需要再求一次前缀和这样的话时间复杂度最坏就达到了O(n)所以我们就需要用到树状数组去实现这些功能树状数组与线段树的区别他们之间的关系可以用包含关系来描述也就是线段树包含了树状数组能够使用的功能但树状数组的使用比线段树的使用快了很多倍树状数组就像是一个专精的工具效率高但利用面相对于线段树不广。树状数组的注意点以及图解注意点树状数组的下标为从1开始对于树状数组的实现我们通常采用一维数组来存储数列其中奇数下标都为树状数组的第零层也就是log2(lowbiti)层偶数下标为树状数组的log2(lowbiti)层提前创建两个数组a[N]存原来给定的序列tr[N]存构建的树状数组构建的树状数组的详细图树状数组实现(3个核心函数)函数一lowbit()函数)其中lowbit的作用是求二进制下最低位的1后面有多少个0假如有k个0那么就会返回2^k具体实现int lowbit(int x){return x(-x);
}//是二进制的每个数位“与”的结果
//例如 010 000 111函数二add()函数对于add函数他主要的作用就是用来修改某一个位置上元素的值当然我们在构建树状数组的时候就可以用该函数去构建树状数组具体实现void add(int x,int v){for(int ix;in;ilowbit(i)) tr[i]y;
}函数三query()函数对于query函数他主要的作用就是用来询问前i个元素的和我们一般用query(r)-query(l-1)来表示[l,r]区间的和具体实现int query(int x){int sum0;for(int ix;i1;i-lobit(i)) sumtr[i];return sum;
}题目动态求连续区间和题目详细代码详解#includeiostream
using namespace std;const int N1e56;int a[N],tr[N];
int n,m;int lowbit(int x){return x(-x);
}void add(int x,int v){for(int ix;in;ilowbit(i)) tr[i]v;
}int query(int x){int res0;for(int ix;i;i-lowbit(i)) restr[i]; return res;
}int main(){cinnm;for(int i1;in;i) scanf(%d,a[i]);for(int i1;in;i) add(i,a[i]);while(m--){int k,x,y;scanf(%d%d%d,k,x,y);if(1k) add(x,y);else printf(%d\n,query(y)-query(x-1));}return 0;
}
