关于可持久化线段树的一些体会

这个玩意我搞了一个月 终于在jzw dalao的指引下成功的搞懂了qwq

说一下几点注意事项

1.如果写指针版,那么最好使用定位new运算符从预分配的栈空间上分配内存(new 从heap里分配内存比较耗时)

2.代表一个节点的结构体里 没用的东西尽量别写(可持久化数据结构十分耗内存)

注意c++的对象内存对齐

3.查找区间第k小时 设当前节点为node 如果k<=node->leftChd->value 那么就从node->leftChd里查找第k小 直到找到叶子结点

如果k>node->leftChd->value  就从node->rightChd里查找第k-node->leftChd->value

代码:https://www.luogu.org/problemnew/show/3834

/*
 * To change this license header, choose License Headers in Project Properties.
 * To change this template file, choose Tools | Templates
 * and open the template in the editor.
 */
/* 
 * File:   main.cpp
 * Author: Ytong
 *
 * Created on 2017年11月10日, 下午2:54
 */
#p\
r\
a\
g\
m\
a GCC optimize("O3")
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
//#define DEBUG
using namespace std;

using int_t = int;
const int_t LARGE = 200000;
const int_t INF = 0x7ffffff;

struct Node {
    int_t begin = 0;
    int_t end = 0;
    int_t value = 0;
    Node* leftChd = nullptr;
    Node* rightChd = nullptr;
};
Node* roots[LARGE + 1];

char buff[sizeof (Node)*1000000 * 7];
const int_t LENGTH = sizeof (buff) / sizeof (Node);
int_t used = 0;

Node* nextNewNode() {
    if (used < LENGTH) {
        return new (buff + (used++) * sizeof (Node)) Node;
    } else {
        return new Node;
        
    }
}
int_t data[LARGE + 1];

struct Num {
    int_t val;
    int_t id;
} nums[LARGE + 1];

Node* buildTree(int_t left, int_t right) {
    Node* node = nextNewNode();
    node->begin = left;
    node->end = right;
    if (left == right) {
        node->value = 0;
    } else {
        int_t mid = (left + right) / 2;
        node->leftChd = buildTree(left, mid);
        node->rightChd = buildTree(mid + 1, right);
        node->value = node->leftChd->value + node->rightChd->value;
    }
    return node;
}

void buildNextTree(Node*& node, int_t pos, Node* x) {
    node = nextNewNode();
    node->begin = x->begin;
    node->end = x->end;
    if (node->begin == node->end && node->begin == pos) {
        node->value = x->value + 1;
    } else if (pos >= node->begin && pos <= node->end) {
        buildNextTree(node->leftChd, pos, x->leftChd);
        buildNextTree(node->rightChd, pos, x->rightChd);
        node->value = node->leftChd->value + node->rightChd->value;
    } else {
        node = x;
    }
}

int_t query(int_t begin, int_t end, int_t k) {
    Node* leftPtr = roots[begin - 1];
    Node* rightPtr = roots[end];
    while (leftPtr->begin != leftPtr->end) {
        int_t leftSize = rightPtr->leftChd->value - leftPtr->leftChd->value;
        if (k <= leftSize) {
            leftPtr = leftPtr->leftChd;
            rightPtr = rightPtr->leftChd;
        } else {
            k -= (rightPtr->leftChd->value - leftPtr->leftChd->value);
            leftPtr = leftPtr->rightChd;
            rightPtr = rightPtr->rightChd;
        }
    }
    return leftPtr->begin;
}
int_t orders[LARGE + 1];

int main(int argc, char** argv) {
    ios::sync_with_stdio(false);
    int_t n, m;
    cin >> n>>m;
    for (int_t i = 1; i <= n; i++) {
        cin >> nums[i].val;
        nums[i].id = i;
    }
    sort(&nums[1], &nums[n + 1], [&](Num & x, Num & y)->bool {
        return x.val < y.val;
    });
    for (int_t i = 1; i <= n; i++) orders[nums[i].id] = i;
    roots[0] = buildTree(1, n);
    for (int_t i = 1; i <= n; i++) {
        buildNextTree(roots[i], orders[i], roots[i - 1]);
    }
    for (int_t i = 1; i <= m; i++) {
        int_t left, right, k;
        cin >> left >> right>>k;
        //   cout << "query " << left << " " << right << " " << k << " = " << query(left, right, k) << endl;
        cout << nums[query(left, right, k)].val << endl;
    }
    return 0;
}