add persistable_segment_tree.md #71
Conversation
valderyaya
commented
May 14, 2023
•
valderyaya
commented
- Read Contribute to NTHU-CPP.
- Rebase to the latest main branch.
- List all the references.
- Successfully build the website by mdBook with no error after the change.
- Exclude any irrelevant files.
- Link to the issue which is related to your change.
- Review the content by myself.
- Pass tests/CI.
|
latex語法待改 |
|
@harry900831 Waiting review |
There was a problem hiding this comment.
- There's a lot of space for improvement on this article.
- Please read more online resources instead of only reading something like OI-wiki, CSDN blog....
- The explanation is not clear, the code need to refactor, the format is incorrect, .... Please re-organize the whole article
- You may refer to others PR or the article that has been merged into NTHU-CPP to know that what kind of article you have to write.
- https://nthu-cp.github.io/NTHU-CPP/graph/lca.html
- https://nthu-cp.github.io/NTHU-CPP/math/introduction_to_generating_function.html
- https://nthu-cp.github.io/NTHU-CPP/graph/introduction_to_AP_bridge.html
- https://nthu-cp.github.io/NTHU-CPP/graph/introduction_to_BCC.html
- https://nthu-cp.github.io/NTHU-CPP/greedy/basic.html
- https://nthu-cp.github.io/NTHU-CPP/sqrt/sqrt_decomposition.html
- There's some application for persistent segment tree, If possible, you should also mention it. For example: https://codeforces.com/blog/entry/64628
- Please fix markdownlint and textlint.
- You should better put more effort on this otherwise it might not be merged into NTHU-CPP in the summer vacation.
|
|
||
|
|
||
|
|
||
|
|
There was a problem hiding this comment.
why are you modifying these lines?
| @@ -26,10 +26,15 @@ | |||
| - [Arithmetic Function Revisit](math/revisit_arithmetic_function.md) | |||
| - [Miscellaneous]() | |||
| - [C++ Programming Tips]() | |||
|
|
|||
| - [Data Structures]() | |||
| - [Persistable Segment Tree](data_structures/persistable_segment_tree.md) | |||
There was a problem hiding this comment.
Please rebase to the latest main branch and put this under Data structure section
There was a problem hiding this comment.
- Data Structure
- Segment Tree
- Persistent Segment Tree (Please find out that is the best translation for this keyword)
- Segment Tree
| @@ -0,0 +1,550 @@ | |||
| # 持久化線段樹 | |||
| >先備知識：線段樹，一點圖論名詞 | |||
There was a problem hiding this comment.
You don't have to mention this
| # 持久化線段樹 | ||
| >先備知識：線段樹，一點圖論名詞 | ||
|
|
||
| > 各位在網路搜尋資料的時候可能會出現**主席樹**這種說法，主席樹指的是持久化權值線段樹 |
There was a problem hiding this comment.
This should not be told as this form
|
|
||
| > 各位在網路搜尋資料的時候可能會出現**主席樹**這種說法，主席樹指的是持久化權值線段樹 | ||
| ## 引入 | ||
| 對於持久化線段樹，最經典的題目莫過於**區間第k小**，題目的內容是這樣的：給定一個長度為$n$的整數序列，每次詢問一個閉區間 \\([l,r]\\)和一個整數\\(k\\)，求在此區間裡第k小的數字是多少。 |
| ### [TIOJ 1827 Yet another simple task \^____\^](https://tioj.ck.tp.edu.tw/problems/1827) | ||
|
|
||
| #### 題目敘述 | ||
|
|
||
|
|
||
| 給定一個長度為 \\(N\\) 的整數序列 \\(B\\)。有 \\(M\\) 筆詢問，對於每組詢問 \\((P, K)\\)，求最小的答案 \\(S\\) 滿足至少有 \\(K\\) 個元素滿足以下條件 | ||
|
|
||
| - \\(|P - i| \leq S\\) | ||
| - \\(B_i \leq S\\) | ||
|
|
||
| \\(1 \leq N, M \leq 10^5 \\) | ||
| \\(1 \leq K, B_i \leq N \\) | ||
| \\(0 \leq P \lt N\\) |
There was a problem hiding this comment.
Please follow the format:
https://nthu-cp.github.io/NTHU-CPP/sqrt/sqrt_decomposition.html
| ```cpp | ||
| #include<bits/stdc++.h> | ||
| //#include<bits/extc++.h> | ||
| //using namespace __gnu_pbds; | ||
| using namespace std; | ||
| #define F first | ||
| #define S second | ||
| typedef long long ll; | ||
| #define REP(i,n) for(register int i=0;i<(n);++i) | ||
| #define REP1(i,a,b) for(register int i=(a);i<=(b);++i) | ||
| #define em emplace_back | ||
| #define mkp make_pair | ||
| #define pb push_back | ||
| #define ALL(x) (x).begin(),(x).end() | ||
| #define pii pair<int,int> | ||
| #define pll pair<ll,ll> | ||
| #define Rosario ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); | ||
| //#define lb(x) (x&-x) | ||
|
|
There was a problem hiding this comment.
Why the coding style are different in the whole article?
Please use your own code....
There was a problem hiding this comment.
Please remove the useless Marco and your personal habit on the code....
| ### [洛谷 P2633 Count on a tree](https://www.luogu.com.cn/problem/P2633) | ||
|
|
||
| #### 題目敘述 | ||
| 給定一棵 \\(n\\) 個節點的樹，每個點有一個權值。有 \\(m\\) 個詢問，每次給你 \\(u,v,k\\)，你需要回答 \\(u \text{ xor last}\\) 和 \\(v\\) 這兩個節點間第 \\(k\\) 小的點權。 | ||
|
|
||
| 其中 \\(\text{last}\\) 是上一個詢問的答案，定義其初始為 \\(0\\)。 | ||
|
|
||
| \\(1\le n,m \le 10^5\\)， 點權在 \\([1,2^{31}-1]\\) 之間。 |
There was a problem hiding this comment.
You use a lot of problem from 洛谷 but I believe there should also have lots of problem that can be solved by persistent segment tree on codeforces or atcoder
| ## References | ||
| https://blog.csdn.net/yanweiqi1754989931/article/details/117380913 | ||
|
|
||
| https://oi-wiki.org/ds/persistent-seg/ | ||
|
|
||
| https://tioj.ck.tp.edu.tw/problems/1827 | ||
|
|
||
| https://www.luogu.com.cn/problem/P2617 | ||
|
|
||
| https://www.luogu.com.cn/problem/P2633 | ||
|
|
||
| https://www.luogu.com.cn/problem/P3168 | ||
|
|
||
| https://codeforces.com/problemset/problem/1771/F |
There was a problem hiding this comment.
Please use bullet list, problem shouldn't be list on the references.
| https://blog.csdn.net/yanweiqi1754989931/article/details/117380913 | ||
|
|
||
| https://oi-wiki.org/ds/persistent-seg/ |
There was a problem hiding this comment.
If you only read the above two resources, it's pretty obvious that you have to do more research...
|
why are you closing this? |
我在修改的時候可能不小心動到了什麽，我再試著改回來 |
|
@harry900831 我在pull rebase的時候遇到了一些問題，所以我把branch刪掉重建了，這導致了pull request被關了，好像沒辦法restore，我可以修改完之後再新開一個pull request嗎 |
|
Sure. |
