线段树及树状数组及其相关问题
pokerjest
3238
发布于 未知归属地
树状数组线段树C++cpp学习分享

简介

介绍有关线段树及树状数组的题目，会不定期更新。
树状数组能够解决的问题 线段树都可以解决 反之不成立

解决的问题类型：连续和查询问题

问题提出：给定一个n个元素的数组，设计一个数据结构，支持查询操作query(L,R)即计算[L,R]区间内元素的和。
法一：暴力出奇迹（一般不会出现）

for (int i = 0; i < n; i++)sum += a[i];

法二：前缀和法

int sum[MAXN];

for (int i = 1; i < n; i++)sum[i] = sum[i-1]+a[i];//预处理
sum[r]-sum[l-1];//每次查询时的操作

法三：树状数组法
现在 再增加一个要求add(P, V)即给P位置上的值增加V
这时候就需要使用我们的二叉索引树(树状数组)

理解树状数组之前 先来理解一个函数lowbit(int i)即一个数二进制表达式中的最右边一位所对应的值是什么 举个例子：


然后该如何求出这个值呢？代码中提供了一种简洁的求法即

    int lowbit(int i)
    {
        return i & (-i);
    }

理解这个东西 首先需要知道 计算机里的整数常常采用补码来表示 补码中的负数就是该数按位取反加一后的结果 还用刚才那个例子：

按位取反


加一

通过肉眼比较就能知道-38288和38288只有最右边的1和其后面的0是相同的 因此这两个数按位取教自然就是到我们想要的结果

IMG_20200828_082603.jpg
对于一个节点x 它的左子节点是x-lowbit(x) 它的右子节点是x+lowbit(x)
由他的这个数的结构 我们可以构造一个数组C C的每一元素都是数组中连续一段的和
连续一段就是上图中所画的那些白条所覆盖的地方的和 比如


写到这里相信大家已经注意到了lowbit在其中起着什么样的作用即找出当前应该加上连续的哪段 比如你想查询11

同样的 进行单点增加操作时 也只需要在这几个位置加上相应的数即可
树状数组可以让你在logn的复杂度下 完成对于前缀和的查询 和 对单点的修改

法四：线段树法
为什么有了数组数组还需要介绍线段树法呢？
因为它只能够求解区间连续和的问题能力不够强
现在 再给它增加需求 比如求区间的最大值或者最小值
对于区间求最大值、最小值这种特定的问题 这里再介绍一种简单好写的数据结构叫ST表
dp[i][j]表示从i开始的长度为2的j次方这个区间的最小值 递推式如下

意思就是把前面两段做个比较取最小值
查询操作就是比较两段的大小即可

#define MAXN 1111
int dp[MAXN][MAXN];
int a[MAXN];
int n;
int ST_init()
{
	for (int i = 1; i <= n; i++)dp[i][0] = a[i];
	for (int j = 1; (1 << j) <= n; j++)
		for (int i = 1; i + j - 1 <= n; j++)
			dp[i][j] = min(dp[i][j - 1], dp[1 << (j - 1)][j - 1]);
}
int query(int L, int R)
{
	int k = 0;

	while (1 << (k + 1) < R - L + 1)k++;
	return min(dp[L][k], dp[R - (1 << k)][k]);//两段中的最小值就是他的最小值
}

ST表虽然简单 但是它的缺陷也很明显 就是不能修改 修改就需要重新init 这时候就引出了最强大的线段树 待续未完~

树状数组模板

    #define MAXN 50050
    int n;//元素个数
    int c[MAXN] = {0};//c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]

    int lowbit(int i)
    {
        return i & (-i);
    }

    //返回A[1]+...A[i]的和
    int sum(int i)
    {
        int res = 0;
        while (i > 0)
        {
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }

    //令A[i] += val
    void add(int i, int val)
    {
        while (i <= n)
        {
            c[i] += val;
            i += lowbit(i);
        }
    }

线段树模板（点修改）

#define MAXN 50050
struct Tree
{
	int l, r;
	long long sum;
	long long max_num;
}tree[MAXN << 2];//开个四倍大小的线段树数组
int n, a[MAXN];
using namespace std;
void built(int x, int l, int r)
{//biu~一个线段树
	tree[x].l = l;
	tree[x].r = r;//这就是一个线段啦
	if (l == r)//左端点和右端点相等就是一个点
		tree[x].sum = a[l];
	else
	{
		int mid = (l + r) >> 1;
		built(x << 1, l, mid);//用递归来构造
		built(x << 1 | 1, mid + 1, r);//先左后右
		tree[x].sum += tree[x << 1].sum + tree[x << 1 | 1].sum;//至下而上的形成线段树
	}
}
void update(int x, int position, int val)
{//更新操作
	int L = tree[x].l;
	int R = tree[x].r;//当前节点的区间

	if (L == position && R == position)
		tree[x].sum += val;//如果到了那个点就改变那个点的值
	else
	{//如果没到那个点那就只能递归了
		int mid = (L + R) >> 1;
		if (mid >= position)update(x << 1, position, val);
		else update(x << 1 | 1, position, val);//寻找点的操作
		tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
	}
}
long long query(int x, int l, int r)
{//查询操作
	int L = tree[x].l;
	int R = tree[x].r;

	if (l == L && r == R)
		return tree[x].sum;//找到了这段区间
	else
	{//没找到就继续找呗
		int mid = (L + R) >> 1;

		if (r <= mid)return query(x << 1, l, r);//右边界在中线的右边就向左走
		if (l > mid)return query(x << 1 | 1, l, r);//同样的左边界在中线的左边就向右走
		return query(x << 1, l, mid) + query((x << 1) + 1, mid + 1, r);
	}//两边的结果加起来
}

相关例题以及题解

307. 区域和检索 - 数组可修改
题解（树状数组）

const int maxn = 30000 + 5;//最大元素个数

//返回i的二进制最右边1的值

class NumArray {
private:
    int n;//元素个数
    int c[maxn] = {0};//c[i]==A[i]+A[i-1]+...+A[i-lowbit(i)+1]
public:
    int lowbit(int i)
    {
        return i & (-i);
    }

    //返回A[1]+...A[i]的和
    int sum(int i)
    {
        int res = 0;
        while (i > 0)
        {
            res += c[i];
            i -= lowbit(i);
        }
        return res;
    }

    //令A[i] += val
    void add(int i, int val)
    {
        while (i <= n)
        {
            c[i] += val;
            i += lowbit(i);
        }
    }

    NumArray(vector<int>& nums) {
        n = nums.size();
        for (int i = 0; i < nums.size(); i++)add(i + 1, nums[i]);
    }

    void update(int i, int val) {
        add(i + 1, val - (sum(i + 1) - sum(i)));
        
    }

    int sumRange(int i, int j) {
        return sum(j+1) - sum(i);
    }
};

题解（线段树）

#define MAXN 50050
struct Tree
{
	int l, r;
	long long sum;
	long long max_num;
};//开个四倍大小的线段树数组

using namespace std;

class NumArray {
private:
    int n, a[MAXN];
    Tree tree[MAXN << 2];
public:
void built(int x, int l, int r)
{//biu~一个线段树
	tree[x].l = l;
	tree[x].r = r;//这就是一个线段啦
	if (l == r)//左端点和右端点相等就是一个点
		tree[x].sum = a[l];
	else
	{
		int mid = (l + r) >> 1;
		built(x << 1, l, mid);//用递归来构造
		built(x << 1 | 1, mid + 1, r);//先左后右
		tree[x].sum += tree[x << 1].sum + tree[x << 1 | 1].sum;//至下而上的形成线段树
	}
}
void updatee(int x, int position, int val)
{//更新操作
	int L = tree[x].l;
	int R = tree[x].r;//当前节点的区间

	if (L == position && R == position)
		tree[x].sum = val;//如果到了那个点就改变那个点的值
	else
	{//如果没到那个点那就只能递归了
		int mid = (L + R) >> 1;
		if (mid >= position)updatee(x << 1, position, val);
		else updatee(x << 1 | 1, position, val);//寻找点的操作
		tree[x].sum = tree[x << 1].sum + tree[x << 1 | 1].sum;
	}
}
long long query(int x, int l, int r)
{//查询操作
	int L = tree[x].l;
	int R = tree[x].r;

	if (l == L && r == R)
		return tree[x].sum;//找到了这段区间
	else
	{//没找到就继续找呗
		int mid = (L + R) >> 1;

		if (r <= mid)return query(x << 1, l, r);//右边界在中线的右边就向左走
		if (l > mid)return query(x << 1 | 1, l, r);//同样的左边界在中线的左边就向右走
		return query(x << 1, l, mid) + query((x << 1) + 1, mid + 1, r);
	}//两边的结果加起来
}
    NumArray(vector<int>& nums) {
        if (nums.size() == 0)return;
        for (int i = 0; i < nums.size(); i++)a[i+1] = nums[i];
        built(1, 1, nums.size());
    }

    void update(int i, int val) {
        updatee(1, i+1, val);
    }
    
    int sumRange(int i, int j) {
        return query(1, i+1, j+1);
    }
};
评论 (2)