lowbit函数

lowbit函数指的是将元素与元素的补码按位与,即a&-a,这个值返回的是从右数第一个1开始的值

例如 6&-6, 6二进制位为110,所以6的lowbit函数值为10,即十进制下的二

ll lowbit(ll num)
{
    return num&-num;
}

树状数组

首先我们可以把一整个数组分为若干小部分,然后让这几个小部分叠加就可以得到数组总的和。例如,我想求a[91],我可以先求c[88],发现c[88]管理2个数,再找c[86],这样一直进行下去就可以了。

c又是什么呢?例如c[6],它的lowbit函数为2,因此它管理两位数,所以c[6]=a[5]+a[6]

奇数位的c[i]只有他自己,而偶数位c[i]为2的k次方

单点修改

void add(int x, int k) {
while (x <= n) { //不能越界
c[x] = c[x] + k;
x = x + lowbit(x);
}
}

这个函数是把a[x]加上k,小于x的c不用修改

关键是x=x+lowbit(x)

从此图中我们可以看出,要想求偶数位节点大小,需要将所有子节点加起来,先要加自己和比自己小一位的奇数,再加上所有i+lowbit(i)=8的偶数

求和

int getsum(int x) {  // a[1]……a[x]的和
int ans = 0;
while (x >= 1) {
ans = ans + c[x];
x = x - lowbit(x);
}
return ans;
}

建立

void init() {
for (int i = 1; i <= n; ++i) {
t[i] += a[i];
int j = i + lowbit(i);
if (j <= n) t[j] += t[i];
}
}
int kth(int k) {  //权值树状数组查询第k小
int cnt = 0, ret = 0;
for (int i = log2(n); ~i; --i) {
ret += 1 << i;
if (ret >= n || cnt + t[ret] >= k)
ret -= 1 << i;
else
cnt += t[ret];
}
return ret + 1;
}

线段树

含义:线段树指的是将一个区间不断二分所形成的一个二叉树,根结点代表arr[0:N]区间所对应的信息,接着根结点被分为两个子树,分别存储arr[0:(N-1)/2]及arr[(N-1)/2+1:N]两个子区间对应的信息

初始化:注意此处我们对于segmentTree]数组的索引从1开始算起。则对于数组中的任意结点i,其左子结点为2*i,右子结点为2*i + 1,其母结点为i/2。



递归实际意义是先向底层递归,然后从底层向上回溯,p的意思是节点的编号

void build(int s, int t, int p) {
// 对 [s,t] 区间建立线段树,当前根的编号为 p
if (s == t) {
d[p] = a[s];
return;
}
int m = (s + t) / 2;
build(s, m, p * 2), build(m + 1, t, p * 2 + 1);
// 递归对左右区间建树
d[p] = d[p * 2] + d[(p * 2) + 1];
}

区间修改

区间修改指的是把区间内连续多个数同时修改

标记的作用是记录每次、每个节点要更新的值

另一种写法

当使用lazy函数时,会让下一层的数加上相应的数并附上相应懒标记,同时根节点的懒标记将被清除,这样一层层往下就可以让每一个数都加上该值

struct node
{
int sum;
int lz;
}sgm[MAX*4];
#define mid ((l+r)>>1)
#define lc (n << 1)
#define rc (n << 1|1)
voide lazy(int n,int l,int r)
{
/*懒标记的作用是标记当前区间应该加上/减去的值,但是先不直接加,而是进行标记*/
sgm[lc].lz+=sgm[n].lz;
sgm[rc].lz+=sgm[n].lz;
sgm[lc].sum+=(mid-l+1)*sgm[n].lz;
sgm[rc].sum+=(r-mid)*sgm[n].lz;
sgm[n].lz=0;
}

区间查询

这里的push_down就是另一种写法中的lazy

总代码

#include<iostream>
using namespace std;
#define lc (n << 1)
#define rc (n << 1|1)
#define mid ((l+r)>>1)
#define MAX 100
struct node
{
int sum;
int lz;
}sgm[MAX*4];
void lazy(int l,int r,int n)
{
sgm[lc].lz+=sgm[n].lz;
sgm[rc].lz+=sgm[n].lz;
sgm[lc].sum+=(mid-l+1)*sgm[n].lz;
sgm[rc].sum+=(r-mid)*sgm[n].lz;
sgm[n].lz=0;
}
void build(int l,int r,int n,int a[])
{
if(l==r)
{
sgm[n].sum=a[l];
return ;
}
build(l,mid,lc,a);
build(mid+1,r,rc,a);
sgm[n].sum=sgm[lc].sum+sgm[rc].sum;
}
void update(int n,int L,int R,int l,int r,int num)
{
if(L<=l&&R>=r)
{
sgm[n].sum+=(r-l+1)*num;
sgm[n].lz+=num;
return ;
}
lazy(l,r,n);
if(L<=mid)
{
update(lc,L,R,l,mid,num);
}
if(R>mid)
{
update(rc,L,R,mid+1,r,num);
}
sgm[n].sum=sgm[lc].sum+sgm[rc].sum;
}
int ask(int n,int L,int R,int l,int r)
{
int ans=0;
if(L<=l&&R>=r)
{
return sgm[n].sum;
}
lazy(l,r,n);
if(L<=mid)
{
ans+=ask(lc,L,R,l,mid);
}
if(R>mid)
{
ans+=ask(rc,L,R,mid+1,r);
}
return ans;
}
int main()
{
int a[10];
for(int i=1;i<10;i++)
{
a[i]=i;
}
build(1,9,1,a);
for(int i=1;i<40;i++)
{
cout<<sgm[i].sum<<" ";
}
update(1,2,5,1,9,3);
cout<<endl;
cout<<ask(1,1,3,1,9);

return 0;
}