[蓝桥杯学习] 树状树组

发布时间:2024年01月06日

lowbit操作

数字二进制表达中的最低位1以及后面所有的0,函数写法如下:

int lowbit(int x){return x&-x;}

例如说,lowbit(0101100100) = (100)

lowbit(4) = 4? lowbit(6) = 2??

时间复杂度o(1)

树状数组

应用

进行单点修改和区间查询,时间复杂度为O(logn)

结构

进行单点修改

修改t[i],然后 i=i+lowbit(i) ,修改t[i]?

进行区间查询

查询区间和,就拆分成求前缀和,求(a,b),就拆成(1,b)-(1,a-1)

i=i-lowbit(i)

修改和查询函数的代码

注意,一定是 >0

例题

愉悦值的计算就是求区间和

有两个操作,修改和查询,使用树状数组的数据结构。

#include <iostream>
using namespace std;

const int N = 1e7;
using ll = long long;
ll a[N],t[N];
int n;

int lowbit(int x) {return x&-x;}

void update(int k,ll x)
{
  a[k] += x;
  for(int i = k ; i <= n ;i += lowbit(i)) t[i] += x;
}

ll getprefix(int k)
{
  ll res = 0;
  for(int i = k ; i > 0 ; i -= lowbit(i)) res += t[i];
  return res;
}

ll getsum(int l,int r)
{
  return getprefix(r) - getprefix(l-1);
}

ll oper(int k,int n)
{
  return (2*k-n-1)*a[k]-getsum(1,k-1)+getsum(k+1,n);
}


int main()
{
  // 请在此输入您的代码
  int m;
  cin >> n >> m;
  for(int i = 1 ; i <= n ; i++) 
  {
    ll x;
    cin >> x;
    update(i,x);
  }

  while(m--)
  {
    int op;
    cin >> op;
    if(op == 1)
    {
      int x;
      ll z;
      cin >> x;
      cin >> z;
      update(x,z-a[x]);
    }
    else 
    {
      int x;
      cin >> x;
      cout << oper(x,n) << '\n';
    }
  }

  return 0;
}

文章来源:https://blog.csdn.net/weixin_73512213/article/details/135427010
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。