线段树和树状数组

jiulics · 2023-01-03 17:30:37 · 个人记录

关于线段树和树状数组的一些理解

• 树状数组思路很简单，模式固定，只需要考虑基本套路时候需要使用树状数组即可
• 树状数组的最基本操作就是lowvbit

  #define lowbit(x) ((x)&(-x))

• 线段树和树状数组主要利用的知识点就是前缀和和差分

  差分

• 差分主要用于线段树和树状数组的区间修改的问题
• 比如我要再[a,b] 区间修改，让其加上c，此时我只需要让D[a]+c，D[b+1]-c即可

对于线段树主要难的是debug，以下是一些思考

线段树真的好简单 （bushi）啊

A-树状数组

• 基本上来说，树状数组所用到的关键知识就是前缀和和单点修改

前缀和

• 查询前缀和，返回前缀和sum=a[1]+a[2]+...+a[x]

  int sum(int x)
  {
  int ans=0;
  while(x!=0)
  {
      ans+=tree[x];
      x-= lowbit(x);
  }
  return ans;
  }

  单点修改

• 单点修改 修改元素 a[x],使得a[x]=a[x]+d

int add(int x,int k,int n)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}

• ## 线段树 ### 建树

• 对于线段树首先得建一个树，其本质的递归和二分的思想

• 先设left=1,right=n，

• 然后每一次递归，left、mid和mid+1、right。

  void build(int left,int right,int index)
  {
      tree[index].left=left;
      tree[index].right=right;
         if(left==right)
          return ;
      int mid=(right+left)/2;
      build(left,mid,index*2);
      build(mid+1,right,index*2+1);
  }

  单点修改

• 线段树的单点修改

• 看这个节点代表着的区间包括不包括这个点，包括就加上。

  void my_plus(int index,int dis,int k)
  {
      tree[index].num+=k;
      if(tree[index].left==tree[index].right)
          return ;
      if(dis<=tree[index*2].right)
          my_plus(index*2,dis,k);
      if(dis>=tree[index*2+1].left)
          my_plus(index*2+1,dis,k);
  }

  单点查询

• 就是从根节点，一直搜索到目标节点，然后一路上都加上就好了。

  void search(int index,int dis)
  {
      ans+=tree[index].num;
      if(tree[index].left==tree[index].right)
          return ;
      if(dis<=tree[index*2].right)
          search(index*2,dis);
      if(dis>=tree[index*2+1].left)
          search(index*2+1,dis);
  }

  区间修改

• 和线段树区间查询类似，分为三种

• 1、如果当前区间完全属于要加的区间，那么这个区间，也就是节点加上，然后return；

• 2、如果这个区间的right>目标区间的left，那么查询这个区间；

• 3、如果这个区间的left<目标区间的right，也查询这个区间;

  void pls(int index,int l,int r,int k)
  {
      if(tree[index].left>=l && tree[index].right<=r)
      {
          tree[index].num+=k;
          return ;
      }
      if(tree[index*2].right>=l)
         pls(index*2,l,r,k);
      if(tree[index*2+1].left<=r)
         pls(index*2+1,l,r,k);
  }

树状数组例题

• luogu :P3374 【模板】树状数组 1
• 1.本题代码：使用树状数组

#include<bits/stdc++.h>
using namespace std;
#define lowbit(x) ((x)&-(x))
#define endl '\n'
#define int long long
const int INF=0x3f3f3f3f;
using ll=long long;
using ld=long double;
#define PB push_back
#define MK make_pair
#define EB emplace_back
#define rep(i,n,m) for(int i=n;i<=m;i++)
#define rrep(i,n,m) for(ll i = (ll)(m) - 1; i >= (ll)(n); i--)
const int N=10000010;
const int M=1010;
int tree[N];
#define lowbit(x) ((x)&(-x))
int sum(int x)
{
    int ans=0;
    while(x!=0)
    {
        ans+=tree[x];
        x-= lowbit(x);
    }
    return ans;
}
int add(int x,int k,int n)
{
    while(x<=n)
    {
        tree[x]+=k;
        x+=lowbit(x);
    }
}
int solve()
{
    int n,m;
    cin>>n>>m;
    //for(int i=1;i<=n;i++)
    rep(i,1,n)
    {
        int a;
        cin>>a;
        add(i,a,n);
    }
    //for(int i=1;i<=m;i++)
    rep(i,1,m)
    {
        int a,b,c;
        cin>>a>>b>>c;
        if(a==1)
        {
            add(b,c,n);
        }
        if(a==2)
        {
            cout<<sum(c)-sum(b-1)<<endl;
        }
    }
}
signed  main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
    /*int t;
    cin>>t;
    while(t--)
    {
        solve();
    }*/
    solve();

}

区间修改

• 区间修改使用的是差分的思想
• 前面是没有任何区别的，在加的时候有所不同而已

  差分：：

设数组a[]={1,6,8,5,10}，那么差分数组b[]={1,5,2,-3,5}

也就是说b[i]=a[i]-a[i-1];(a[0]=0;)，那么a[i]=b[1]+....+b[i];(这个很好证的)。

假如区间[2,4]都加上2的话