树状数组能处理的问题线段树都能处理(包含关系)

树状数组优点：1.代码短 2.常数小，运行效率高
优先使用树状数组

树状数组：快速的动态求前缀和(logn)

支持操作：

1.给某个位置上的数加上一个数(单点修改)
2.某一个前缀和(区间查询)

仅支持单点修改和区间查询问题，其他问题(如区间修改单点查询，或者区间修改区间查询)需要转化为这个问题进行解决

与前缀和的不同

前缀和是静态的，只能查询O(1)；树状数组能支持修改，并且能查询O(logn)

树状数组基本原理

设原数组为A, 树状数组为C；
对于x位置的数：

1.x的二进制表示最后有k个0，表示x在第k层
2.C[x]表示 (x - 2 ^ k, x] 范围的数的和

公式：

计算2 ^ k：lowbit(x)(x & -x) 返回2^k；

定义：C[x]表示：(x - lobit(x), x]的范围

lobit

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

求1 — x的前缀和

int get(int x)
{
    int sum = 0;
    for(int i = x;i > 0;i -= lobit(i))
        sum += c[i];
    return sum;
}

更新一个A[i]

因为A[i]的改变而发生改变的元素：对于一个x，由前缀和公式可知，x使用过的元素为 x - n * lobit(i)；所以A[i]的改变能影响到 i + n * lobit(i) 位置上的元素

void add(int x, int v) // A[x] + v
{
    for(int i = x;i <= n;i += lobit(i))
        c[i] += v;
}

树状数组建立：利用add函数

for(int i = 1;i <= n;i ++)
{
    int x;
    scanf("%d", &x);
    add(i, x); // a[i] + x；
}

规律

每一个节点只有一个父节点(是一棵树) 证明太难，略
x + lobit(x) 是x的唯一父节点(证明太难，略)
x在第几层，即x有几个末位0，则x有几个子节点

时间复杂度分析：

区间查询操作：从x每次减去一个 lowbit(i)，相当于将二进制表示末尾的1变为0(减去一个末位1)，而最多有log(n)个二进制位，故时间复杂度为 logn

单点修改操作:
对x每次加上一个lobit(i)，相当于加上若干个末位0，最多有logn个二进制位，所以最多加logn次末位0，时间复杂度位 logn

线段树

线段树可以动态的维护一个序列中：一段区间的和、最大值、最小值、均值等性质

另一个应用：扫描线法求矩形面积

油漆面积