给定序列，支持区间加、求区间和。
线段树的基本思路（线段树模板嘛，不懂得看题解第一，dalao讲解超详细的）
#include<bits/stdc++.h>
using namespace std;
#define ll long long
int MAXN=1000001;
unsigned ll n,m,a[MAXN],ans[MAXN<<2],lazytag[MAXN<<2];
开头还用解释吗qaq
inline ll 左儿子
inline ll 右儿子
void 输入
void 传递
void 建树
void 当前处理懒标记
void 传递懒标记
void 更新
ll 求和
//当然在数据较小的时候可以用int，看着顺眼
以上是各函数的框架，都是线段树的基本函数。
int main()
{
输入
建树
while(m--)
{
输入操作选项
case 1:
{
输入xyk
更新
break;
}
case 2:
{
输入xy
输出和
break；
}
}
return 0;
}
主函数的设计思路还是比较简单的，不过要注意输入输出的优化，cincout可能会TLE吧，虽然没试过2333
接下来是填好了的主函数！一定要自己打一遍再看哦~
真的自己打了吗？？？
int main()
{
ll op,x,y,k;
shuru();
buildtree(1,1,n);
while(m--)
{
scanf("%lld",&op);
switch(a1)
case 1:
{
scanf("%lld%lld%lld",&x,&y,&k);
update(x,y,1,n,1,k);
break;
}
case 2:
{
scanf("%lld%lld",&x,&y);
printf("%lld
",query(x,y,1,n,1));
break;
}
return 0;
}
这些函数都是啥？？？接着往下看吧owo
先看比较简单的找左右儿子
根据二叉树的性质
父亲节点fa的左右儿子
分别是 fa<<2 和 fa<<2|1
这是zhaungbi优秀的位运算
表示fa2 和 fa2+1
你可以先不用理解它是什么意思
记住它的含义就好了
void shuru()
{
cin>>n>>m;
for(ll i=1;i<=n;i++)
scanf("%lld",&a[i]);
}
简单可爱的输入
void pushup(ll x)
{
ans[x]=ans[leftchild(x)]+ans[rightchild(x)];
}
void buildtree(int x,int l,int r)
{
lazytag[x]=0;
if(l==r)
{
ans[x]=a[l];
return;
}
ll mid=(l+r)>>1;
build(leftchild(x),l,mid);
build(rightchild(x),mid+1,r);
pushup(p);
}
二分的方法建树
如果是叶子节点，那么它的值就是自己
如果是父亲节点，就是它的儿子的和
初始化懒标记为0，表示暂时没有向下传递的数据
void lazy(ll x,ll l,ll r,ll k)
{
lazytag[x]=lazytag[x]+k;
ans[x]=ans[x]+k*(r-l+1);
lazytag[x]=0;
}
void pushdown(ll x,ll l,ll r)
{
ll mid=(l+r)>>1;
lazy(leftchild(x),l,mid,lazytag[x]);
lazy(rightchild(x),mid+1,r,lazytag[x]);
}
void update(ll L,ll R,ll l,ll r,ll x,ll k)
{
//[L,R]为要求查询区间,查询过程中不能变
if(L<=l && R>=r)
//当前区间被查询区间完全包含
{
ans[x]+=k*(r-l+1);
lazytag[x]+=k;
return;
}
//不完全包含
pushdown(x,l,r);//处理懒标记，排除影响
ll mid=(l+r)>>1;
if(L<=mid)update(L,R,l,mid,leftchild(x),k);
if(R>mid) update(L,R,mid+1,r,rightchild(x),k);
pushup(x);
}
ll querysum(ll a,ll b,ll l,ll r ll x)
{
ll res=0;
//当前区间被查询区间完全包含
if(a<=l && r<=b)return ans[p];
//不完全包含
ll mid=(l+r)>>1;
push_down(x,l,r);
if(a<=mid)res+=querysum(a,b,l,mid,leftchild(x));
if(b>mid) res+=querysum(a,b,mid+1,r,rightchild(x));
return res;
}
接下来求和和更新的操作类似
都是判断所求区间与当前区间的包含关系
完全包含当前区间比较好办
不完全包含的情况用二分查找，降低时间复杂度owo
嘛
测试点信息
1
AC
0ms/2101KB
2
AC
0ms/2121KB
3
AC
0ms/2132KB
4
AC
8ms/2226KB
5
AC
8ms/2242KB
6
AC
8ms/2214KB
7
AC
8ms/2156KB
8
AC
168ms/6953KB
9
AC
160ms/6953KB
10
AC
160ms/6894KB
