一种没什么用的线段树

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

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

懵逼的 题目

传送至 Codevs

扯淡的 题解

复制一下样例来解释吧QwQ

                   ____________21__________   
           _______17_______            ______4________   
         __9__          __8__        __4__           __0__ 
         4   5          6   2        1   3           0   0   
                   _____________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的普通线段树

// 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