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次方

单点修改

llvm
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的偶数

求和

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

建立

excel
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];
  }
}
x86asm
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的意思是节点的编号

arduino
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函数时，会让下一层的数加上相应的数并附上相应懒标记，同时根节点的懒标记将被清除，这样一层层往下就可以让每一个数都加上该值

excel
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

总代码

pgsql
#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;
}