## 【codevs 1080】线段树练习 之 花样解法 原

LOI_xczhw

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstdio>
using namespace std;
const int MAXN = 100000 + 5;
int num[MAXN];
int n,m,q,a,b;
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++)
scanf("%d",&num[i]);
for(int i = 1;i <= n;i ++)
num[i] += num[i - 1];
scanf("%d",&m);
for(int i = 1;i <= m;i ++)
{
scanf("%d %d %d",&q,&a,&b);
if(q == 1)
for(int i = a;i <= n;i ++)
num[i] += b;
else
printf("%d\n",num[b] - num[a - 1]);
}
return 0;
}``````

``````#include<cstdio>
#include<iostream>
#define ll long long
using namespace std;
int num[200010];
struct dc{
int l,r;
}tree[200010*4];

void build(int p,int l,int r)
{
tree[p].l=l,tree[p].r=r;
if(l==r)
{
tree[p].sum=num[l];
return ;
}
int mid=(l+r)/2;
build(p*2,l,mid);
build(p*2+1,mid+1,r);
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

{
{
}
}

void change(int p,int a,int x)
{
if(a==tree[p].l&&tree[p].r==a)
{
tree[p].sum+=x;
return;
}
int mid=(tree[p].l+tree[p].r)/2;
if(a<=mid) change(p*2,a,x);
if(mid<a) change(p*2+1,a,x);
tree[p].sum=tree[p*2].sum+tree[p*2+1].sum;
}

{
if(l<=tree[p].l&&tree[p].r<=r)
{
return tree[p].sum;
}
int mid=(tree[p].l+tree[p].r)/2;
ll ans=0;
return ans;
}
int main()
{
int n;scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&num[i]);
build(1,1,n);
int S;scanf("%d",&S);
while(S--)
{
int s;scanf("%d",&s);
int a,b,x;
if(s==1)
{
scanf("%d%d",&a,&x);
change(1,a,x);
}
else
{
scanf("%d%d",&a,&b);

}
}
return 0;
}
``````

``````#include <iostream>
#include <cstdio>
using namespace std;
const int MAXN = 100000 + 5;
int n,z,a,b,tree[MAXN];
int lowbit(int x)
{
return x & (- x);
}
{
while(x <= n)
{
tree[x] += y;
x += lowbit(x);
}
return;
}
int qzh(int x)
{
int ans = 0;
while(x > 0)
{
ans += tree[x];
x -= lowbit(x);
}
return ans;
}
{
return qzh(t) - qzh(s - 1);
}
int main()
{
scanf("%d",&n);
for(int i = 1;i <= n;i ++)
{
scanf("%d",&z);
}
int m;
scanf("%d",&m);
for(int i = 1;i <= m;i ++)
{
scanf("%d",&z);
if(z == 1)
{
scanf("%d %d",&a,&b);
}
else
{
scanf("%d %d",&a,&b);
}
}
return 0;
}``````

``````#include <iostream>
#include <cmath>
#include <cstring>
using namespace std;

const int MAXN = 1000000 + 5;
const int MAXM = 10000 + 5;
int treee[MAXN],M;
void init(int n)
{
M = 1 << ((int)log2(n + 1) + 1);
for(int i = M + 1; i <= M + n; i++)
cin >> treee[i];
for(int i = M - 1; i >= 1; i--)
treee[i] = treee[i << 1] + treee[i << 1 | 1];

}
{
for(treee[x += M] += a,x >>= 1;x;x >>= 1)
{
treee[x] = treee[x << 1] + treee[x << 1 | 1];
}
return;
}
{
int ans = 0;
for(s = s + M - 1,t = t + M + 1;s ^ t ^ 1;s >>= 1,t >>= 1)
{
if(~s & 1) ans += treee[s ^ 1];
if(t & 1) ans += treee[t ^ 1];
}
return ans;
}
int n,m,q,a,b;
int main()
{
cin >> n;
init(n);
cin >> m;
for(int i = 1;i <= m;i ++)
{
cin >> q >> a >> b;
if(q == 1)
{
}
if(q == 2)
{
}
}
return 0;
}``````

zkw太强大了……

splay

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
const int MAXN = 100000 + 5;
struct tr
{
tr *ch[2],*f;
int val,sz,cnt;
bool dir()
{
return f -> ch[1] == this;
}
void maintain()
{
cnt = ch[0] -> cnt + ch[1] -> cnt + val;
sz = ch[0] -> sz + ch[1] -> sz + 1;
}
void setc(tr *x,int v)
{
(ch[v] = x) -> f = this;
}
}tree[MAXN],*root,*null;
int tot;
tr* newdot(int v,tr *f)
{
tr *p = tree + tot++;
p -> val = p -> cnt = v;
p -> sz = 1;
p -> ch[0] = p -> ch[1] = null;
p -> f = f;
return p;
}
void init()
{
tot = 0;
null = newdot(0,null);
null -> sz = 0;
root = null;
return;
}
void rot(tr *x)
{
tr *p = x -> f;
int d = x -> dir();
p -> f -> setc(x,p -> dir());
p -> setc(x -> ch[d ^ 1],d);
p -> maintain();
x -> setc(p,d ^ 1);
if(root == p)
root = x;
return;
}
void splay(tr *x,tr *to = null)
{
while(x -> f != to)
if(x -> f -> f == to)
rot(x);
else
x -> dir() == x -> f -> dir() ? (rot(x -> f),rot(x)) : (rot(x),rot(x));
return;
}
{
tr *x = root;
while(true)
{
x -> cnt += v;
if(x -> ch[0] -> sz + 1 == p)
{
x -> val += v;
break;
}
int d = x -> ch[0] -> sz + 1 <= p;
if(d)
p -= x -> ch[0] -> sz + 1;
x = x -> ch[d];
}
splay(x);
return;
}
int sum(int xx,int yy)
{
int p = xx - 1;
tr *x = root;
while(true)
{
int d = x -> ch[0] -> sz + 1 <= p;
if(x -> ch[0] -> sz + 1 == p)
break;
if(d)
p -= x -> ch[0] -> sz + 1;
x = x -> ch[d];
}
splay(x);
p = yy + 1;
while(true)
{
int d = x -> ch[0] -> sz + 1 <= p;
if(x -> ch[0] -> sz + 1 == p)
break;
if(d)
p -= x -> ch[0] -> sz + 1;
x = x -> ch[d];
}
splay(x,root);
return x -> ch[0] -> cnt;
}
int num[MAXN];
void build(int l,int r,tr * &x,tr *f)
{
if(l > r)return;
int mid = (l + r) >> 1;
x = newdot(num[mid],f);
build(l,mid - 1,x -> ch[0],x);
build(mid + 1,r,x -> ch[1],x);
x -> maintain();
return;
}
int n,m,q,a,b;
int main()
{
init();
scanf("%d",&n);
for(int i = 2;i <= n + 1;i ++)
scanf("%d",&num[i]);
build(1,n + 2,root,null);
scanf("%d",&m);
for(int i = 1;i <= m;i ++)
{
scanf("%d %d %d",&q,&a,&b);
if(q == 1)
else
printf("%d\n",sum(a + 1,b + 1));
}
return 0;
}``````

1. 编号从0开始
2. 别忘了判断出界
3. 任何时间要保证l < r
4. sqrt……

``````#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>
#include <cmath>
#define KILL puts("haha")
using namespace std;

const int MAXN = 100000 + 5;
int sum[MAXN],num[MAXN];
int n,m;
int M;
void init()
{
M = sqrt(n) + 1;
for(int i = 0;i < n;i ++)
if(i % M == 0)
sum[i / M] = num[i];
else
sum[i / M] += num[i];
return;
}
void change(int x,int y)
{
num[x] += y;
sum[x / M] += y;
return;
}
int sumer(int x,int y)
{
int ans = 0;
while(x % M && x < y)//就是这里的这句
ans += num[x++];
while(y % M && y > x)
ans += num[y--];
ans += num[y];//别忘了闭区间……
while(x < y)
ans += sum[x / M],x += M;
return ans;
}
int q,a,b;
int main()
{
scanf("%d",&n);
for(int i = 0;i < n;i ++)
scanf("%d",&num[i]);
init();
scanf("%d",&m);
for(int i = 1;i <= m;i ++)
{
scanf("%d %d %d",&q,&a,&b);
if(q == 1)
change(a-1,b);
else
printf("%d\n",sumer(a-1,b-1));
}
return 0;
}``````

### LOI_xczhw

2016/04/02
159
1

ACM的竞赛性强,因此自己应该和自己的实际应用联系起来.适合自己的才是好的,有的人不适合搞算法,喜欢系统架构,因此不要看到别人什么就眼红,发挥自己的长处,这才是重要的. 第一阶段：练经典常用...

long0404
2015/06/24
0
0

2013/01/06
190
0

05/01
0
0
splay的各种操作与简易讲解

litble
2017/07/07
0
0

java快递电子面单打印接口对接demo

20分钟前
3
0
fasjtjson文档

https://github.com/alibaba/fastjson/wiki/JSONField

jirak
20分钟前
3
0
Mybatis中插入多条记录

21分钟前
3
0

23分钟前
3
0

23分钟前
3
0