拥有域名后怎么搭建网站,网站推广方案怎么写的,响应式网站建设必推全网天下,石家庄网站建设培训树状数组
lowbit
在学习树状数组之前#xff0c;我们需要了解lowbit操作#xff0c;这是一种位运算操作#xff0c;用于计算出数字的二进制表达中的最低位的1以及后面所有的0。 写法很简单#xff1a;
int lowbit#xff08;int x#xff09;#xff5b;return x 我们需要了解lowbit操作这是一种位运算操作用于计算出数字的二进制表达中的最低位的1以及后面所有的0。 写法很简单
int lowbitint xreturn x -x这是利用了计算机存储整数的特性来写的在计算机中整数都使用补码进行存储原理不做深究记住怎么写即可。
树状数组基础
树状数组是一种可以“动态求区间和”的树形数据结构但并没有真正地构造出边来所以是“树状”的。 基础的树状数组可以实现对区间和的单点修改和区间查询时间复杂度均为Ologn. 树状数组所需的东西非常简单就一个数组intN大小和我们所需要维护的数组大小一样即可
先看下树状数组的结构 其中ti存储a数组中一段区间的和具体区间 怎么算呢 我们定义是让ti存储以i结尾且区间大小为 lowbiti的区间的和。 ∑ j i − lowbit ( i ) 1 i a i \sum_{ji-\text{lowbit}(i)1}^{i} a_i ji−lowbit(i)1∑iai 我习惯于叫i-lowbiti1i为i的管辖区间。
怎么进行单点修改 举个例子假如我要修改a3让他加上x在右边这个图中我们可以看出我们应该修改 t3t4和t8共3个节点。因为这三个节点的管辖区间内都包含3这个节点 但是我们如何从3开始去找到348呢 只需要进行lowbit操作即可二进制性质。 3 lowbit3 4 4 lowbit4 8 …
怎么进行区间查询 第一步我们将其拆为两个区间的差举个例子我们要查询区间37的和就要拆分为sum17 sum12回想一下前缀和的写法~ 现在问题变为如何查询1k的和 假如我们要求sum17我们从右图可以知道结果为t7t6t4这是怎么得到的呢 通过lowbit可 7 - lowbit7 6 6 - lowbit6 4
于是我们可以直接得到树状数组最重要的两个函数update()和getprefix(). 大功告成
// 给 a[k] 增加 x
void update(int k, int x) {for (int i k; i n; i lowbit(i)) {t[i] x;}
}// 返回区间 [1, k] 的和
int getprefix(int k) {int res 0;for (int i k; i 0; i - lowbit(i)) {res t[i];}return res;
}
殷老师排队 思路将式子转化用树状数组模拟题意
#includebits/stdc.h
using namespace std;
const int N 1e59;
using ll long long ;
ll a[N],t[N],n,m;
int lowbit(int x){return x-x;
}void update(int k,int x){a[k] x;for(int ik;in;ilowbit(i)){t[i] x;}
}ll getPrefix(int k){ll res 0;for(int ik;i0;i-lowbit(i)){rest[i];}return res;
}ll getSum(int l,int r){return getPrefix(r) - getPrefix(l-1);
}int b(int i){return (2*i - n - 1)*a[i] - getSum(1, i-1) getSum(i1, n);
}int main( ){ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);cinnm;for(int i1;in;i){int x;cinx;update(i,x);}while(m--){int op;cinop;if(op1){int k,b;cinkb;update(k, -a[k]b);}else{int i;cini;coutb(i)\n;}}return 0;
}
