树状数组

定义

树状数组是一种支持单点修改和动态前缀和。

原理

树状数组利用数组下标的二进制特性来维护信息。

int low_bit(const int x)  
{  
    return  x & -x;  
}

low_bit(x) 表示 x 的二进制中最低位的 1 所代表的值。
tree[i] 维护的是 [i - lowbit(i) + 1, i] 的和。

查询

int query(int index)  
{  
    int sum = 0;  
    while (index > 0)  
    {  
        sum += tree[index];  
        index -= low_bit(index);  
    }  
    return sum;  
}

例：

int sum = query(100); // 查询数组[1,100]的和

单点修改

void update(int index, int value)
{
	while(index <= n)
	{
		tree[index] += value;
		index += low_bit(index);
	}
}

例：

update(5,10); // a[5] += 10

模版

struct BinaryIndexedTree  
{  
    int tree[MAX_N], sum;  
    static int LowBit(const int& x) { return x & -x; }  
  
	BinaryIndexedTree()  
	{  
	    memset(tree, 0, sizeof(tree));  
	}
	
    void Update(int index, const int& value)  
    {  
       while (index <= n)  
          tree[index] += value, index += LowBit(index);  
    }  
  
    int Query(int index) const  
    {  
       sum = 0;  
       while (index > 0)  
          sum += tree[index], index -= LowBit(index);  
       return sum;  
    }  
};

应用

---

统计某个区间中不同数字的个数

思路：在区间[L, R]中，将一个数字最后出现的位置设为1，那么prefix[R] - prefix[L - 1]就是答案。
实现：遍历数组[1, N]，对于没有出现过的数字，标记为1，同时记下这个数字最后出现的位置。对于已经出现过的数字，将最后出现的位置标记为0，再将当前位置标记为1。