2013-team6/BIT

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

{{{
一维树状数组
}}}

{{{
创建
BITree t;
清空
t.clear();
将第 k 个数增加 d
t.add(k, d);
查询 0 < i <= k 的 sum(a[i])
t.sum(k);

注意事项：lowbit(0)会陷入死循环，因此数组从1开始
}}}
{{{
const int MAXN = 20005;
typedef int DATA;

struct BITree{
    DATA bit[MAXN];
    void clear(){
        memset(bit, 0, sizeof(bit));
    }
    DATA query(int p){
         int ret=0;
         for (int k = p ; k>0; k -= k & (-k))
             ret+=bit[k];
         return ret;
    }
    void add(int p, DATA q , int n){
         for (int k = p; k<=n; k += k & (-k))
             bit[k]+=q;
    }
    DATA query2(int p,int n){
         int ret=0;
         for (int k = p ; k<=n; k += k & (-k))
             ret+=bit[k];
         return ret;
    }
    void add2(int p, DATA q){
         for (int k = p; k>0; k -= k & (-k))
             bit[k]+=q;
    }
};
}}}

----
== 总结 ==
=== by gantians ===
----
== 练习 ==
=== by gantians ===
 hdu1166  单点更新，区间查询

 hdu1556  区间更新，单点查询

 hdu1541  排序+坐标转化为下标（也可以离散化）

 hdu2689  逆序对。向上更新，向下统计（小于当前值的个数）向下更新，向上统计（大于当前值的个数）

一维树状数组

创建
BITree t;
清空
t.clear();
将第 k 个数增加 d
t.add(k, d);
查询 0 < i <= k 的 sum(a[i])
t.sum(k);
注意事项：lowbit(0)会陷入死循环，因此数组从1开始

const int MAXN = 20005;
typedef int DATA;
struct BITree{
    DATA bit[MAXN];
    void clear(){
        memset(bit, 0, sizeof(bit));
    }
    DATA query(int p){
         int ret=0;
         for (int k = p ; k>0; k -= k & (-k))
             ret+=bit[k];
         return ret;
    }
    void add(int p, DATA q , int n){
         for (int k = p; k<=n; k += k & (-k))
             bit[k]+=q;
    }
    DATA query2(int p,int n){
         int ret=0;
         for (int k = p ; k<=n; k += k & (-k))
             ret+=bit[k];
         return ret;
    }
    void add2(int p, DATA q){
         for (int k = p; k>0; k -= k & (-k))
             bit[k]+=q;
    }
};

---

总结

by gantians

---

练习

by gantians

hdu1166 单点更新，区间查询

hdu1556 区间更新，单点查询

hdu1541 排序+坐标转化为下标（也可以离散化）

hdu2689 逆序对。向上更新，向下统计（小于当前值的个数）向下更新，向上统计（大于当前值的个数）