线段树与树状数组
线段树
题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某区间每一个数加上 k。
- 求出某区间每一个数的和。
输入格式
第一行包含两个整数n*,*m，分别表示该数列数字的个数和操作的总个数。
第二行包含 nn 个用空格分隔的整数，其中第 ii 个数字表示数列第 ii 项的初始值。
接下来 mm 行每行包含 33 或 44 个整数，表示一个操作，具体如下：
1 x y k：将区间[x,y]内每个数加上 k。2 x y：输出区间[x,y]内每个数的和。
输出格式
输出包含若干行整数，即为所有操作 2 的结果。
输入输出样例
输入 #1
5 5
1 5 4 2 3
2 2 4
1 2 3 2
2 3 4
1 1 5 1
2 1 4
输出 #1
11
8
20
线段树的关键数据结构：
num[MAX]
ans[MAX << 2]
lazy[MAX << 2]
其中num作为输入的数字集合，ans作为线段树的集合，lazy作为懒标记，懒记录了当前区间的更新值。
update操作
//其中x-y是当前更新区间，l-r是当前划分区间的两端，k是更新值，p是区间段值
void update(int x, int y, int l, int r, int k, int p)
{
if (x <= l && y >= r)
{
//更新当前区间值，并阻断下方的更新，做到懒更新
ans[p] += (ll)k * (r - l + 1);
lazy[p] += k;
return;
}
//伸展操作，如果当前层不是更新的最底层，则向下伸展更新下一层
spread(p, r, l);
int mid = r + l >> 1;
if (x <= mid)
update(x, y, l, mid, k, p << 1);
if (y > mid)
update(x, y, mid + 1, r, k, p << 1 | 1);
//更新时只有最底层在更新，递归返回后更新上层
ans[p] = ans[p << 1] + ans[(p << 1) + 1];
}
spread操作
//伸展操作，将lazy[p]传递给子结点，并更新子结点
void spread(int p, int r, int l)
{
if (lazy[p] != 0)
{
int mid = (r + l) >> 1;
ans[p << 1] += lazy[p] * (mid - l + 1);
ans[(p << 1) | 1] += lazy[p] * (r - mid);
lazy[p << 1] += lazy[p];
lazy[(p << 1) | 1] += lazy[p];
lazy[p] = 0;
}
}
read操作
ll read(int x, int y, int l, int r, int p)
{
if (x <= l && y >= r)
{
return ans[p];
}
//有时候需要读入未更新的底层，所以需要伸展
spread(p, r, l);
int mid = r + l >> 1;
ll sum = 0;
if (x <= mid)
sum += read(x, y, l, mid, p << 1);
if (y >= mid + 1)
sum += read(x, y, mid + 1, r, p << 1|1);
return sum;
}
建树操作
//建立线段树
void build(int p, int l, int r)
{
if (l == r)
{
ans[p] = num[l];
return;
}
int mid = l + r >> 1;
build((p << 1), l, mid);
build((p << 1) + 1, mid + 1, r);
ans[p] = ans[p << 1] + ans[(p << 1) + 1];
}
树状数组
题目描述
如题，已知一个数列，你需要进行下面两种操作：
- 将某一个数加上 x
- 求出某区间每一个数的和
输入格式
第一行包含两个正整数 n,m，分别表示该数列数字的个数和操作的总个数。
第二行包含 n个用空格分隔的整数，其中第 i个数字表示数列第 i项的初始值。
接下来 m行每行包含 33 个整数，表示一个操作，具体如下：
1 x k含义：将第 x个数加上 k2 x y含义：输出区间 [x,y][x,y] 内每个数的和
输出格式
输出包含若干行整数，即为所有操作 22 的结果。
输入输出样例
输入 #1
5 5
1 5 4 2 3
1 1 3
2 2 5
1 3 -1
1 4 2
2 1 4
输出 #1
14
16
参考博客，讲的非常好
https://blog.csdn.net/TheWayForDream/article/details/118436732
#include<iostream>
#include<cstring>
#define lowbit(x) (x&(-x))
using namespace std;
typedef long long ll;
const int Maxn=1e6+5;
int a[500005];
int d[Maxn]={0};//d[i]的值，d[i]表示第i和i-1个数的差值
ll c[Maxn];
int n,m;
int update(int pos,int k)//pos表示修改点的位置,K表示修改的值也即+K操作
{
for(int i=pos;i<=n;i+=lowbit(i))
c[i]+=k;
return 0;
}
ll ask_qujian(int pos)//返回区间pos到1的总和
{
ll ans=0;
for(int i=pos;i;i-=lowbit(i)) ans+=c[i];
return ans;
}
int main()
{
memset(c,0,sizeof(c));
scanf("%d %d",&n,&m);
a[0]=0;
for(int i=1;i<=n;i++)
{
scanf("%d",&a[i]);
d[i]=a[i]-a[i-1];
update(i,d[i]);
}
for(int i=1;i<=m;i++)
{
int choice,x,y,k;
scanf("%d",&choice);
if(choice==1)
{
scanf("%d %d %d",&x,&y,&k);
update(x,k);
update(y+1,-k);
}
else
{
scanf("%d",&x);
printf("%lld\n",ask_qujian(x));
}
}
return 0;
}
#include<iostream>
#define lowbit(x) (x&(-x))
typedef long long ll;
using namespace std;
int c[2000006];
int n,m;
ll ans;
int add_dandian(int x,int k)
{
for(int i=x;i<=n;i+=lowbit(i))
c[i]+=k;
}
int search(int begin,int end)
{
for(int i=end;i;i-=lowbit(i))
ans+=c[i];
for(int i=begin-1;i;i-=lowbit(i))
ans-=c[i];
return 0;
}
int main()
{
scanf("%d %d",&n,&m);
for(int i=1;i<=n;i++)
{
int number;
scanf("%d",&number);
add_dandian(i,number);
}
for(int i=1;i<=m;i++)
{
int choice,x,y;
scanf("%d %d %d",&choice,&x,&y);
if(choice==1) add_dandian(x,y);
else
{
ans=0;
search(x,y);
printf("%lld\n",ans);
}
}
return 0;
}