【算法】树状数组

文章目录

• 一、基本概念
• 二、核心操作
• 三、常见应用

  一、基本概念

  树状数组用于动态维护一段区间，操作的时间复杂度为 O ( l o g n ) O(logn) O(logn)

  定义： t [ i ] = [ i − l o w b i t ( i ) + 1 , i ] t[i] = [i - lowbit(i) + 1, i] t[i]=[i−lowbit(i)+1,i] 区间和

  二、核心操作

  树状数组下标建议从 1 1 1 开始

  单点修改：给 a [ x ] + v a[x] + v a[x]+v

  void add(int x, int v)
  { for(int i = x; i <= n; i += lowbit(i)) t[i] += v;
  }
  

  区间查询：求 [ 1 , x ] [1, x] [1,x] 区间和

  int query(int x)
  { int res = 0;
      for(int i = x; i; i -= lowbit(i)) res += t[i];
      return res;
  }
  

  lowbit

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

  三、常见应用

  树状数组维护差分，可以实现动态的区间修改和单点查询

  区间修改：给 [ l , r ] [l, r] [l,r] 区间每个数加上 c c c

  add(l, c);
  add(r + 1, -c);
  

  单点查询：求 a [ x ] a[x] a[x]

  query(x)