树状数组模块(个人模板)
树状数组模块
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;
}