谨慎C语言中树数组的每一步操作

在C语言中，树数组是开发中常用的操作，而它的出现可以大大降低数字序列的复杂度，下面是爱站技术频道小编和大家分享的谨慎C语言中树数组的每一步操作。

C语言树状数组的实例详解

最近学了树状数组，给我的感觉就是 这个数据结构好神奇啊^_^

首先她的常数比线段树小，其次她的实现复杂度也远低于线段树 （并没有黑线段树的意思=-=）

所以熟练掌握她是非常有必要的。。

关于树状数组的基础知识与原理网上一搜一大堆，我就不赘述了，就谈一些树状数组的应用好了

1，单点修改，求区间和

#define lowbit(x) (x&-x) // 设 x 的末尾零的个数为 y , 则 lowbit(x) == 2^y 
void Update(int i,int v) // 初始化与单点修改 
{
  while(i  0)
  {
    res += c[i] ;
    i -= lowbit(i) ;
  }
  return res ;
}

2，区间修改，单点查询

这里要用到差分的思想

创建一个差分数组c[]，令c[i] = a[i] - a[i-1] （a[i] 表示原本的第i个数）

则a[i] = ( a[i] - a[i-1] ) + ( a[i-1] - a[i-2] ) + ...... + ( a[2] - a[1] ) +a[1]

         = c[i] + c[i-1] + ...... + c[2] + c[1]

所以单点查询变成了区间求和

那么区间修改怎么办呢 ？

我们看这样一个例子：

a 1 3 4 5 7 10

c 1 2 1 1 2 3

若我们令区间[2,4]加2，则

a 1 5 6 7 9 10

c 1 4 1 1 2 1

我们可以发现只有c[2]和c[5]的数值改变了，其实原理也很好想，区间内的前后元素差是不变的，只有（区间第一个元素与前一个元素的差） 和 （区间后第一个元素与区间末尾元素的差） 改变了。所以区间修改问题变成了单点修改问题。

  for(int i=1;i

（洛谷有对应的模板题 P3374 与 P3368）

通过爱站技术介绍的谨慎C语言中树数组的每一步操作，我们程序员要谨慎开发时候走的每一步，这可能会导致后面的开发后遇到不同的问题。