A + B
显然,这道题可以转换为区间长度为2的区间求和问题
既然是区间求和,又不愿写前缀和、树状数组,我们就练练线段树吧。
CODE:
#include<iostream>
#include<cstdio>
#include<algorithm>
#define ll long long
#define INF 0x3f3f3f3f
using namespace std;
struct node
{
ll l;
ll r;
ll sum;
}st[20];
void build(ll,ll,ll);
ll find1(ll,ll,ll);
ll a[3];
int main()
{
ios::sync_with_stdio(false);
for(int i = 1;i <= 2;++i)
{
cin >> a[i];
}
build(1,1,2);
cout << find1(1,1,2) << endl;
return 0;
}
void build(ll p,ll l,ll r)
{
st[p].l = l,st[p].r = r;
if(l == r)
{
st[p].sum = a[l];
return ;
}
ll mid = (l + r) >> 1;
build(p << 1,l,mid);
build((p << 1) + 1,mid + 1,r);
st[p].sum = st[p << 1].sum + st[(p << 1) + 1].sum;
}
ll find1(ll p,ll l,ll r)
{
if(l <= st[p].l&&r >= st[p].r)
{
return st[p].sum;
}
ll mid = (st[p].l + st[p].r) >> 1;
ll ans = 0;
if(l <= mid) ans += find1(p << 1,l,r);
if(r > mid) ans += find1((p << 1) + 1,l,r);
return ans;
}
.....