活跃农民
- 积分
- 420
- 大米
- 颗
- 鳄梨
- 个
- 水井
- 尺
- 蓝莓
- 颗
- 萝卜
- 根
- 小米
- 粒
- 学分
- 个
- 注册时间
- 2017-7-28
- 最后登录
- 1970-1-1
|
写了 fenwick tree 和 segment tree with lazy propagation 两个解法。通过这题我学会了lazy propagation
- class FenwickTree{
- public:
- // idea:
- // 1. toggle [i,j] is equivalent to toggle [1,i] then toggle[1,j]
- // 2. let tree[i] stores the **total number of toggles** in the corresponding binary range
- // 3. for a bulb x,
- // (i) sum of toggles in [1,x] is odd, if x belongs to [i,j] and x being toggled odd times, i.e. [1,j] will covers x odd times, while [1,i] covers x even times (or 0 time).
- // (ii) sum of toggles in [1,x] is even, if x is out of[i,j] or x is in [i,j] && x being toggled even times.
- FenwickTree(int n_) {
- n = n_;
- tree.resize(n+1, 0);
- }
- vector<int> tree;
- int n;
- void update(int i, int add) {
- for(; i > 0; i -= i&(-i))
- tree[i] += add;
- }
-
- int query(int i) {
- int ans = 0;
- for(; i <= n; i += i&(-i))
- ans += tree[i];
- return ans;
- }
-
- bool isOn(int i) {
- return query(i) & 1;
- }
-
- void toggle(int start, int end) {
- update(start-1, 1);
- update(end, 1);
- }
-
- void run() {
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- toggle(2,5);
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- toggle(3,8);
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- toggle(4,6);
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- }
- };
- class SegmentTree{ // muse use lazy propagation to guarantee log(n) complexity for update() on a range of indices.
- // worst case space complexity O(4*N) with lazy propagation.
- // to learn lazy propagation: http://www.geeksforgeeks.org/lazy-propagation-in-segment-tree/
- public:
- struct TreeNode{
- int lb, ub, count;
- TreeNode *left, *right;
- TreeNode(int lb_, int ub_) {
- lb = lb_;
- ub = ub_;
- count = 0;
- left = right = nullptr;
- }
- };
- TreeNode* root;
- int n;
- unordered_map<TreeNode*, int> lazy;
-
- SegmentTree(int n_) {
- n = n_;
- }
-
- TreeNode* build(int lb, int ub){
- if(lb > ub) return nullptr;
- TreeNode* node = new TreeNode(lb, ub);
- if(lb == ub) return node;
- int mid = lb + (ub - lb) / 2;
- node->left = build(lb, mid);
- node->right = build(mid+1, ub);
- return node;
- }
-
- void update(TreeNode* node, int lo, int hi, int add) {
- if(lazy[node] != 0) {
- node->count += (node->ub - node->lb + 1) * lazy[node];
- if(node->left) lazy[node->left] += lazy[node];
- if(node->right) lazy[node->right] += lazy[node];
- lazy[node] = 0;
- }
- if(!node || node->ub < lo || node->lb > hi) return;
- if(lo <= node->lb && node->ub <= hi) {
- node->count += (node->ub - node->lb + 1) * add;
- if(node->left) lazy[node->left] += add;
- if(node->right) lazy[node->right] += add;
- return;
- }
- update(node->left, lo, hi, add);
- update(node->right, lo, hi, add);
- node->count = (node->left ? node->left->count : 0) + (node->right ? node->right->count : 0);
- }
-
- int query(TreeNode* node, int start, int end){
- if(lazy[node] != 0) {
- node->count += (node->ub - node->lb + 1) * lazy[node];
- if(node->left) lazy[node->left] += lazy[node];
- if(node->right) lazy[node->right] += lazy[node];
- lazy[node] = 0;
- }
- if(!node || start > node->ub || end < node->lb) return 0;
- if(start <= node->lb && node->ub <= end) return node->count;
- return query(node->left, start, end) + query(node->right, start, end);
- }
-
- void toggle(int start, int end) {
- update(root, start, end, 1);
- }
- bool isOn(int i) {
- return query(root, i, i) & 1;
- }
- void run() {
- root = build(1, n);
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- toggle(2,5);
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- toggle(3,8);
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- toggle(4,6);
- for(int i = 1; i <= n; i++) cout << isOn(i) << " ";
- cout << endl;
- }
- };
- int main() {
- FenwickTree ft(10); // 10 bulbs
- ft.run();
- cout << "----------" << endl;
- SegmentTree st(10);
- st.run();
- }
复制代码 |
|