现在的位置: 首页 > 综合 > 正文

树状数组两种基本的模式

2017年05月28日 ⁄ 综合 ⁄ 共 714字 ⁄ 字号 评论关闭

树状数数组基本的两种模式:

第一,对初始数组a[i]中的某一元素修改,查询某个区间内的所有的和,(时间复杂度都为logn)。(插点问线)

第二,随时修改数组中a[i]中的某个区间的值(O(1)的时间复杂度),查询某一个元素的值(logn的时间复杂度)。(插线问点)

第一种模式,已经在上一篇文中提到,有兴趣可以点击打开链接

这里重点学习第二种模式。修改某一区间的值,查询某一个元素的值。

在我们这里被叫做插线问点。

如果说第一模式中c[i]中存储的是a[i-2^k+1]到a[i]的和,那么在第二模式中存储的是a[i-2^k+1]到a[i]中,每个点的值。

那么对于插入某一区间([a,b])的某值(c),那么我们就在[1-a]插入-c,在[1,b]插入c就可以。

具体代码:

void Modify(int i,int date){
    while(i>0){
        c[i]+=date;
        i-=lowbit(i);
    }
}

上面的函数就是修改区间1-i的值date。

那么具体操作就是:

Modify(a-1,-date);
Modify(b,date);

那么以上就是对区间[a,b]进行修改的具体操作。

那么,怎么去某一点的值呢?这就更简单了。

int sum(int x){
    int ans=0;
    while(i<=n){
        ans+=c[i];
        i+=lowbit(i);
    }
    return ans;
}

这就是树状数组的两种模式。

那么,我们也可以用数组数组求逆序对数。

用树状数组求逆序对数,就是一个在线的插点问线问题。


树状数组是一种小巧的数据结构。但是,他始终是一种数据结构,而数据结构仅仅是用来辅助解题来的。也就是,在学习树状数组的过程中要注意他的应用方面。

树状数组还有很多的应用,有待学习。

抱歉!评论已关闭.