树状数组(BIT)

2024-10-06 22:39:10

树状数组

树状数组是在线段树的结构上改造而来数据结构，主要用于完成：

给定一个初始值全为0的数列

①给定i，计算返回a1+a2+……+ai的值

②给定i和x，执行ai+=x

BIT的求和

ll sum(int i)

{

	ll s = 0;

	while (i > 0)

	{

		s += bit[i];

		i -= i & -i;

	}

	return s;

}

BIT的值更新

void add(int i, int x)

{

	while (i <= n)

	{

		bit[i] += x;

		i += i & -i;

	}

	return;

}

最新文章

热门文章