1.18~1.19蚯蚓(未完），树状数组（区间修改（差分数组），定点查询）（定点修改，区间查询），线段树（未完）

P2827 [NOIP2016 提高组] 蚯蚓

啥玩意破题这么乱，n个初始蚯蚓，一共要操作m次，蚯蚓长度增加q,uv来确定切割的程度

就是切割为maxx，一个为maxx*u/v,一个为maxx-maxx*u/v

t是一个时间跨度，就是把m分成T份的跨度

每操作一次，即切割一次，就会产生一个新蚯蚓，一共操作m次，那最后就多产生m个新蚯蚓，最后就是n+m个蚯蚓

操作就是，每次从里面出队一个最长的，然后入队两个新的，同时让队里的元素都增加q

这时mlogm的解法

需要每次操作后，都给集合里元素+q,

但实际上只有被操作的不加q，其他的都加q，实际上相当于被操作的-q,即相对的，其他人都加，被操作的不加，就相当于被操作的-q

P3374 【模板】树状数组 1

#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 5e5 + 5;
int n, m, arr[maxn], temp, temp1,temp2;
int lowbit(int x) {
    return x & -x;
}
void add(int i, int num) {
    while (i <= n) {
        arr[i] += num;
        i += lowbit(i);
    }
}
int search(int k) {
    int ans = 0;
    while (k >= 1) {
        ans += arr[k];
        k -= lowbit(k);
    }
    return ans;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> temp;
        add(i, temp);
    }
    for (int i = 1; i <= m; i++) {
        cin >> temp >> temp1 >> temp2;
        if (temp == 1) {
            add(temp1, temp2);
        }
        else {
            cout << search(temp2) - search(temp1-1) << endl;
        }
    }
    return 0;
}

就是需要注意，树状数组类似于前缀和，在求区间的时候，不能是直接右端点减去左端点，这样的话会失去左端点的端点值，应该是temp2-(temp1-1)?

这个操作的原理就是，先让自己都取反，那么自己和自己的反码相与结果肯定是0，然后反码再加1，加1的时候，如果加的位置是0，那么就说明原来是1，与出来是1，就定位到了1；如果是1，说明原来是0，那么此时反码发生进位，该位变为0，和原码相与依然是0，下一位加1，直到遇到第一个是0的地方就不继续进位了，就会使那个0变为1，原码同样位置也是1，就返回了这个最低位的1的二进制数

就是查询与修改，查询的话就向下查询，直到二进制里没1；修改就是向上修改，直到超过数组大小

树状数组的区间查询，就是前缀和，1~右端点减去1~左端点

树状数组整体是连续的，就是说越往后的数据求和完后所代表的区间长度与大小也就越大，只不过是序号所代表的那一段序列大小是可能小的，但其序号本身大，本身的二进制数大

1 2 1 4 1 2 1 8

1 10 11 100 101 110 111 1000

那就是说求和的时候，就是看1的数量，1的数量越多，那么要求和的区间段数也就越多，一直求和，直到二进制数里没有1

树状数组中每个元素都代表一个区间，i是这个区间的编号，且i对应着原数组中的第i个数据，即树状数组中的元素b[i](为某一段区间和）至少包含原数组中的第i个数据的大小

某个序列b[i]，它的序列长度为lowbit(i),就是以原数据i为终点，往前划lowbit(i)个元素

?

如果计算14的区间长度和，

lowbit(14)表示的是树状数组中序号为14的点所对应的区间长度

14-lowbit(14)=12

就是如果要求出数组中某个数据所对应的区间长度，就lowbit一下就能知道

第二行数据区间长度为2，则lowbit为2?

?这个数组就是树状数组

之所以能去掉，是因为如果要用到的话，用上面一层的数字肯定更好，不能用到的话，也只是用前面的数据，所以就是说每层的第偶数个数字是没用的，要用到的话上面一层的数字更好用，在求和的时候?

线段树是一种二叉搜索树，与区间树相似，它将一个区间划分成一些单元区间，每个单元区间对应线段树中的一个叶结点。

使用线段树可以快速的查找某一个节点在若干条线段中出现的次数，时间复杂度为O(logN）。

线段树

P3368 【模板】树状数组 2

不能直接在add上修改是因为毕竟是树状数组，要保证大的也要被加上，如果直接是修改右端点的话，就会导致天花板变了，使上层的数据没有被加上就出错了

正确的就是依然是全加，这样可以保证是全都加上的，然后再让区间右端点后的都再加上-y,这样就保证了实现固定区间的修改

需要注意的是，在树状数组中add里做修改，修改的就是单点上的值，而不是区间整体的值，

就是说，虽然树状数组每个元素指的是一段一段的区间，但是在做修改的时候，即调用add时，实际上是只修改了一个值，一个本质的值，一个最底层的值变化，导致与其有关的所有值的变化，但如果是要修改一个区间的值，即要让区间整体完成加减，只修改一次是不行的

这就要用到差分数组

差分实际上描述的就是相对的，?

就第一个模板题是单点修改，区间查询

单点修改通过调用一次add,区间查询就是s(y)-s(x-1)

第二个模板题是区间修改，单点查询

要区间修改的话，还是存储元数据的树状数组，那么一次add是肯定不行的，就是要等同于区间内元素数量的add才可以

所以就是用差分数组，对差分来构建树状数组

就是说，变化的量大小记录在一个数组当中，然后要查询的话，就直接让原数据加上更改的记录即可

就是基于这个性质

差分数组里，要求某一点的修改值，就是都从头到尾加起来即可，然后修改值再加原始数据就是新的值

#include<iostream>
#include<iomanip>
#include<vector>
#include<string>
#include<algorithm>
#include<queue>
using namespace std;
const int maxn = 5e5 + 5;
int n, m, arr[maxn], temp, x, y, k, in[maxn];
int lowbit(int x) {
    return x & -x;
}
void add(int i, int num) {
    while (i <= n) {
        arr[i] += num;
        i += lowbit(i);
    }
}
int search(int k) {
    int ans = 0;
    while (k >= 1) {
        ans += arr[k];
        k -= lowbit(k);
    }
    return ans;
}
int main() {
    cin >> n >> m;
    for (int i = 1; i <= n; i++) {
        cin >> in[i];
    }
    for (int i = 1; i <= m; i++) {
        cin >> temp;
        if (temp == 1) {
            cin >> x >> y >> k;
            add(x, k);
            add(y + 1, -k);
        }
        else {
            cin >> x;
            cout << search(x) + in[x] << endl;
        }
    }
    return 0;
}

线段树，树状数组