高级数据结构学习笔记 / Data Structure(updating)

树状数组

  查询操作:O(logn)

  修改操作:O(logn)

 

#define lowbit(x) (x & -x)

int tr[N]; // 树状数组

// 添加c个大小为x的数值
void add(int x, int c)
{
    for(int i = x; i <= n; i += lowbit(i)) tr[i] += c;
}

// 求数值大小在1~x的数值的和
int sum(int x)
{
    int res = 0;
    for(int i = x; i; i -= lowbit(i)) res += tr[i];
    return res;
}

 

上一篇:6. 类再生


下一篇:java泛型学习教程,java泛型的使用,java泛型类和泛型方法