学习笔记_ codevs 1080 线段树练习 [重口味线段树(单点修改)]

一种没什么用的线段树

上课,啥都不会啊woc…
[woc这是搜索?]
[woc这啥玩意?]
[woc还能这么做?]

那我能怎么办我也很绝望啊QAQ…于是去水题…正好翻到曾经的ppt…[诶这个好像挺好玩啊]…于是….
还有为啥我的重口味这么慢啊QAQ

懵逼的 题目

传送至 Codevs

扯淡的 题解

复制一下样例来解释吧QwQ

1
2
3
4
          ____________21__________   
_______17_______ ______4________
__9__ __8__ __4__ __0__
4 5 6 2 1 3 0 0
1
2
3
4
            _____________01_____________   
_______10______ ______11______
__100__ __101__ __110__ __111__
1000 1001 1010 1011 1100 1101 1110 1111

emm…是不是让dalao您相信上面是一颗线段树有点难…
那么就让我们运用 [指鹿为马排序] 的思想: “这是不是一棵线段树?” “啊是是是你先把刀放下QAQ”
众所周知一个编号为i的节点的父亲为(i >> 1),左儿子为(i << 1),右儿子为((i << 1) | 1)
其兄弟为(i ^ 1)
一个在原始序列中编号为i的点,在线段树中的编号为i + m(m为大于等于n的最小的2的整次方数)
以上是基础姿势…就是没写过重口味的dalao们也一定知道了QAQ
下面就是具体的实现了QAQ(什么?您问我什么是重口味线段树?您只要知道她很快不就结了?)

建树

既然我们已经知道了原始序列在线段树中的位置…那就直接输入到线段树里好咯(省去了递归找叶子的过程)然后就像 噶韭菜(划掉) 回溯一样,给每一个非叶子节点(编号1~(n - 1))赋值;

噶噶噶噶噶噶韭菜!

查询

查询的基础就是兄弟节点的编号xor一下为1(因为只有最后一位不同) 左儿子的编号最后一位都为0,右儿子的编号最后一位都为1(dalao: 这不废话QAQ)
因为父亲节点存储的是两个儿子的和, 所以为了不重复,左边界只能加上右儿子,右边界只能加左儿子,所以查询的操作就是从底层的两个边界向上找,右边遇到左儿子就加上,左边遇到右儿子也加上(然后变成当前节点的父亲),直到这两个边界成为兄弟(这时候如果再加就会有重复: 结合上面的图理解的QAQ)

修改(什么?您问我区间修改?我这么弱怎么可能会啊QAQ)

修改相对简单,直接找到叶子节点,再”回溯”到根节点,在路径上经过的节点上都进行修改

沙茶的 代码

流输入/出毁青春…还不如用scanf的普通线段树

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
// codevs 1080.cpp : 定义控制台应用程序的入口点。
//

#include "stdafx.h"
#include <iostream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <vector>
#define MAXN (100000 + 5)
using namespace std;
int a[8 * MAXN];
int n;
void js();//建树
void xg(int, int);//修改
int cx(int, int);//查询(洋文不好的辣鸡的函数名QAQ)
int main()
{
int srn;
cin >> srn;
n = 1;
while (n < srn)
{
n <<= 1;
}
for (int i = 1;i <= srn; i++)
{
cin >> a[n + i];
}
js();
int m;
cin >> m;
int e, srx, sry;
for (int i = 1; i <= m; i++)
{
cin >> e >> srx >> sry;
if (e == 1)
{
xg(srx, sry);
}
else
{
cout << cx(srx, sry) << endl;
}
}
return 0;
}
void js()
{
for (int i = n - 1; i >= 1; i--)
{
a[i] = a[(i << 1)] + a[(i << 1) | 1];
}
}
void xg(int w, int z)
{
int xn = n + w;
while (xn)
{
a[xn] += z;
xn >>= 1;
}
}
int cx(int l, int r)
{
int re = 0;
for (int i = l - 1 + n, j = r + n + 1; (i ^ j) != 1;i >>= 1, j >>= 1)
{
if (!(i & 1))
re += a[i ^ 1];
if (j & 1)
re += a[j ^ 1];
}
return re;
}
/*
6
4 5 6 2 1 3
4
1 3 5
2 1 4
1 1 9
2 2 6
*/

By 什么都不会的 Cansult

GG