专栏首页owent树状数组模块(个人模板)

树状数组模块(个人模板)

树状数组模块

ACM个人模板

POJ 2155 题目测试通过

/**
 * 树状数组模块
 * 下标从0开始
 */
typedef long DG_Ran;
typedef long DG_Num;
const DG_Num DG_MAXN = 1005;

//2^n
DG_Num LowBit(DG_Num n)
{
    return n & (-n);
}
//获取父节点索引
DG_Num DGFather(DG_Num n)
{
    return n + LowBit(n + 1);
}
//获取小的兄弟节点索引
DG_Num DGBrother(DG_Num n)
{
    return n - LowBit(n + 1);
}
//查找增加树状数组前pos项和
//参数(树状数组[in],索引[in],初始赋0即查找前n项和[out])
//复杂度:log(n)
void DGFind(DG_Ran *g,DG_Num pos,DG_Ran &sum)
{
    sum += *(g + pos);
    if(pos >= LowBit(pos + 1))
        DGFind(g, pos - LowBit(pos + 1), sum);
}
//查找对应线性数组元素
//参数(树状数组[in],索引[in]).
//返回值:对应线性数组元素log(n)
//复杂度:log(n)
DG_Ran DGFindEle(DG_Ran *g,DG_Num pos)
{
    DG_Ran a = 0 , b = 0;
    DGFind(g, pos, a);
    if(pos)
    {
        DGFind(g,pos - 1,b);
        return a - b;
    }
    else
        return a;
}
//树状数组,增加节点
//参数:树状数组[out],原数组大小[in],新增线性数组值[in]
//复杂度:log(n)
DG_Ran DGAdd(DG_Ran *g,DG_Num n,DG_Ran val)
{
    *(g + n) = val;
    DG_Num a = n;
    DG_Num b = 1;
    while((a & (~b)) != a)
    {
        *(g + n) += *(g + a - 1);
        a &= (~b);
        b <<= 1;
    }
    return n + 1;
}
//构建树状数组
//参数:线性数组[in],数组大小[in],树状数组[out]
//复杂度:nlog(n)
DG_Ran DGCreate(DG_Ran *g,DG_Num n,DG_Ran *tg)
{
    DG_Num i;
    *tg = *g;
    for(i = 1 ; i < n ; i ++)
        DGAdd(tg,i,*(g + i));
    return n;
}
//修改指定位置值
//参数:线性数组[in],数组位置[in],数组大小[in],新值[in]
//复杂度:log(n)
DG_Ran DGEdit(DG_Ran *g,DG_Num pos,DG_Num n,DG_Ran val)
{
    DG_Num f = DGFather(pos);
    DG_Ran o = *( g + pos );
    *( g + pos ) = val;
    if(f < n)
    {
        DG_Ran fv = val - o + *( g + f );
        DGEdit(g, f, n, fv);
    }
    return n;
}

//树状数组的翻转(树状数组的应用)
//一维  复杂度log(n)
//小于等于指定位置的元素的翻转<=pos
void DGDown1(DG_Ran g[],DG_Num pos,DG_Ran av)
{
    while(pos >= 0)
        g[pos] += av , pos = DGBrother(pos);
}
//获取位置pos的元素翻转次数
DG_Ran DGCUp1(DG_Ran g[],DG_Num pos , DG_Num n)
{
    DG_Ran t = 0;
    while(pos < n)
        t += g[pos] , pos = DGFather(pos);
    return t;
}
//二维  复杂度(log(n))^2
//小于等于指定位置的元素的翻转(0,0)->(x,y)
void DGDown2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y,DG_Ran av)
{
    while(x >= 0)
    {
        DG_Num tmp = y;
        while (tmp >= 0)
        {
            g[x][tmp] += av;
            tmp = DGBrother(tmp);
        }
        x = DGBrother(x);
    }
}
//获取位置(x,y)的元素翻转次数
DG_Ran DGCUp2(DG_Ran g[][DG_MAXN],DG_Num x ,DG_Num y , DG_Num n)
{
    DG_Ran t = 0;
    while(x < n)
    {
        DG_Num tmp = y;
        while (tmp < n)
        {
            t += g[x][tmp];
            tmp = DGFather(tmp);
        }
        x = DGFather(x);
    }
    return t;
}

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • POJ PKU 2155 Matrix 解题报告

    题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2155

    owent
  • JQuery扩展插件--提示信息

    https://github.com/owt5008137/SimpleMetro

    owent
  • Lnmp yum 安装脚本 (for CentOS)

    心情大好,给VPS升级了一下系统,然后自己配了LNMP安装脚本,用yum源安装的话更新比较方便点哈 ​​这个过程挺麻烦啊,所以果断要记下来,以防以后要用到 ...

    owent
  • POJ PKU 2155 Matrix 解题报告

    题目链接:http://acm.pku.edu.cn/JudgeOnline/problem?id=2155

    owent
  • 腾讯携手昆明打造智慧出行新体验 | 数字文旅周报22期(7.22-7.28)

    ? 腾讯携手昆明打造智慧出行新体验 7月22日,腾讯公司与昆明公交集团有限责任公司达成合作,乘车码全量上线昆明公交,覆盖全市368条线路约4800辆公交车,...

    腾讯文旅
  • 明日开讲 | 腾讯文旅云端大讲堂第二期“智慧”来袭!

    ? 随着国内疫情基本得到控制和好转,文旅产业逐渐进入了疫后复苏阶段。同时,近期国家相关部门多次提出要大力推进包括5G、大数据中心、人工智能在内的“新基建”建设...

    腾讯文旅
  • HTML被恶意注入JS弹广告

    继续查看http://45.126.123.80:118/t.php 一堆代码,获取各种信息。。。

    Light413
  • 腾讯签约教育部 “云+校园”成云计算与人才的第一连接器

    为了进一步响应《国家教育事业发展“十三五”规划》,促进创新型人才的培养并助推产业发展,国家教育部日前与腾讯正式签署合作备忘录,将围绕“新工科”人才培养、创新创业...

    WOW彩笔er
  • Leetcode【817、876、1019】

    直接将数组转化为集合,然后遍历一次链表。令 ans = 0,flag = True:

    echobingo
  • 福利来一枚:虚拟云服务器

    逆天博客所作的服务器还有1天就过期了,发挥点余热,送个没有部署过的同志练练手(本来准备还有7天的时候放出来的,忘记。。。) ? 说来惭愧,博客开了一年了,没怎么...

    逸鹏

扫码关注云+社区

领取腾讯云代金券