线段树-点修区查
翻博客的时候突然发现线段树好像一个没有，我就准备把线段树给讲一下
分三个章节
点修区查
区修区查
区修区查（带乘法）
今天这一章比较简单，最多就区查稍微要动一点脑子
题目简介
输入n和m，n代表数的个数，m代表查询次数
接下来输入n个数，第i的数的值为a[i]
然后是m次查询,每次查询输入三个数op,x,y
当op为1时,表示将第x个数加上y
当op为2时,表示求x到y的区间和
今天的代码大概就是实现这么个功能
首先来看建树
我们开一个结构体用来存线段树,里面有三个变量
ans,l,r
l和r表示的是当前区间的左边界和右边界,ans存的就是区间和
这么说可能有点不清楚
我们画个图
借助上面这个图,大概能知道线段树的构造
而我们也知道,一颗二叉树由左至右依次从一开始标记数字,一个点x的左孩子编号为2*x,而右孩子为2*x+1,因此,我们可以大致推出线段树的建树代码
void build(int p,int l,int r){f[p]={a[l],l,r};//存储当前点if(l==r)return;//如果到了叶子结点,就returnint mid=(l+r)>>1;//中分,分出左右子树build(lc,l,mid);//遍历左子树build(rc,mid+1,r);//遍历右子树f[p].ans=f[lc].ans+f[rc].ans;//求和
}然后这里的lc和rc刚刚上面已经说了,分别是2*p和2*p+1
#define lc p<<1
#define rc p<<1|1树建完了,我们再来看点修
我们要修改的点,肯定是原数组中的点,所以在这颗线段树里一定是叶子结点,因为不是叶子的点都存储的是区间和。
而叶子结点又有一个特点，因为它只有一位，所以左边界和右边界的值是一样的，这样一来就很好判断了。
只要遍历到的当前点左边界是x，右边界也是x，就可以确定它是我们要修改的点，修改它之后，在按照建树的方法，中分，求区间和，进行向上修改就行了
void change(int p,int x,int k){if(f[p].l==x&&f[p].r==x){f[p].ans+=k;return;}int mid=f[p].l+f[p].r>>1;if(mid<x)change(rc,x,k);if(mid>=x)change(lc,x,k);f[p].ans=f[lc].ans+f[rc].ans;//向上修改区间和
}这里说一下，就是中间两个if语句，是用来精确范围的，如果小了，就往大的找，如果大了，就往小的找，总会找到x的
好的，下面就是最后一项，区间查询了
我们求的任何区间，只要在范围内，都是可以用线段树中的元素拼凑出来的
就拿上面那个图来举例，1-2的区间直接可以得到，1-3的区间则可以用1-2的区间加3得到
所以，我们可以得出结论，求区间和，只需要遍历线段树，只要遍历到的点代表的区间被完全包含，就直接加上这个区间的和,当然,这种方法是不会出现重复的啦
然后强调一下这里精确范围的条件
首先还是中分得到mid
如果mid比 L 大,就要往左边靠,直到贴到L为止
反之,如果mid小于R,就要往右边靠
区查的代码放下面了
int out(int p,int l,int r){if(f[p].l>=l&&f[p].r<=r){return f[p].ans;}int ans=0;int mid=f[p].l+f[p].r>>1;//记得在靠的同时记录区间和,不然就废了if(l<=mid)ans+=out(lc,l,r);if(r>mid)ans+=out(rc,l,r);return ans;
}现在核心代码都出示在这里了,拼拼凑凑就可以实现了
#include<bits/stdc++.h>
#define lc p<<1
#define rc p<<1|1
#define int long long
using namespace std;
const int N=1e6+5;
int a[N];
struct node{int ans,l,r;
}f[4*N];
int n,m;
void build(int p,int l,int r){f[p]={a[l],l,r};if(l==r)return;int mid=(l+r)>>1;build(lc,l,mid);build(rc,mid+1,r);f[p].ans=f[lc].ans+f[rc].ans;
}
int out(int p,int l,int r){if(f[p].l>=l&&f[p].r<=r){return f[p].ans;}int ans=0;int mid=f[p].l+f[p].r>>1;if(l<=mid)ans+=out(lc,l,r);if(r>mid)ans+=out(rc,l,r);return ans;
}
void change(int p,int x,int k){if(f[p].l==x&&f[p].r==x){f[p].ans+=k;return;}int mid=f[p].l+f[p].r>>1;if(mid<x)change(rc,x,k);if(mid>=x)change(lc,x,k);f[p].ans=f[lc].ans+f[rc].ans;
}
signed main(){scanf("%lld%lld",&n,&m);for(int i=1;i<=n;i++)scanf("%lld",&a[i]);build(1,1,n);while(m--){int op;scanf("%lld",&op);int a,b;scanf("%lld%lld",&a,&b);if(op==1){change(1,a,b);}else{printf("%lld\n",out(1,a,b));}}
}