Resource Link:
টিউটোরিয়াল গুলো ক্রম অনুযায়ী সাজানো নাই।
ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-১
ডাটা স্ট্রাকচার: সেগমেন্ট ট্রি-২ (লেজি প্রপাগেশন)
Kaidul blog
blog
Segment tree/ BIT part - 1
লোয়েস্ট কমন অ্যানসেস্টর
Persistent Segment Tree (Part - 01)
Persistent Segment Tree (Part - 02)
A simple approach to segment trees
A simple approach to segment trees, part 2
TopCoder Tutorial
Indian Computing Olympiad
visualgo
E-Maxx : Segment Tree
Algorithm Gym :: Everything About Segment Trees
Efficient and easy segment trees
Segment trees (for beginners)
csacademy
Segment Trees and lazy propagation
Segment Trees
Persistent segment trees – Explained with spoj problems
Persistence Made Simple - Tutorial
CF blog problem list
Problem Link
CF blog problem list
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
| #include<bits/stdc++.h> | |
| using namespace std; | |
| #define mx 100001 | |
| int ar[mx]; | |
| int tree[mx*3]; | |
| void init(int node, int b, int e) | |
| { | |
| if(b == e) | |
| { | |
| tree[node] = ar[b]; | |
| return; | |
| } | |
| int Left = node*2; | |
| int Right = node*2 + 1; | |
| int mid = (b + e)/2; | |
| init(Left, b, mid); | |
| init(Right, mid+1, e); | |
| tree[node] = tree[Left] + tree[Right]; | |
| } | |
| int query(int node, int b, int e, int i, int j) | |
| { | |
| if(i > e || j <b)return tree[node]; | |
| if(b >= i && e <= j) | |
| { | |
| return tree[node]; | |
| } | |
| int Left = node*2; | |
| int Right = node*2 + 1; | |
| int mid = (b+e)/2; | |
| int p1 = query(Left, b, mid, i, j); | |
| int p2 = query(Right, mid+1, e, i, j); | |
| return p1+p2; | |
| } | |
| int update(int node, int b, int e, int i) | |
| { | |
| int ans = 0; | |
| if(i > e || i < b)return ans; | |
| if(b >=i && e <= i) | |
| { | |
| ans = tree[node]; | |
| tree[node] = 0; | |
| return ans; | |
| } | |
| int Left = node*2; | |
| int Right = node*2 + 1; | |
| int mid = (b+e)/2; | |
| update(Left, b, mid, i); | |
| update(Right, mid+1, e, i); | |
| tree[node] = tree[Left] + tree[Right]; | |
| } | |
| void update1(int node, int b, int e, int i, int newvalue) | |
| { | |
| if(i > e || i < b)return; | |
| if(b >=i && e <= i) | |
| { | |
| tree[node] += newvalue; | |
| return; | |
| } | |
| int Left = node*2; | |
| int Right = node*2 + 1; | |
| int mid = (b+e)/2; | |
| update1(Left, b, mid, i,newvalue); | |
| update1(Right, mid+1, e, i, newvalue); | |
| tree[node] = tree[Left] + tree[Right]; | |
| } | |
| int main() | |
| { | |
| int n,q; | |
| cin >> n >> q; | |
| for(int i =1; i <= n; i++) | |
| { | |
| cin >> ar[i]; | |
| } | |
| init(1,1,n); | |
| for(int i = 1; i <= 9; i++) | |
| { | |
| cout<<tree[i]<<" "; | |
| } | |
| cout<<endl; | |
| for(int i = 1; i <= q; i++) | |
| { | |
| int x,idx,v,a,b; | |
| cin >>x; | |
| if(x == 1) | |
| { | |
| cin >> idx; | |
| cout << query(1,1,n,idx+1,idx+1)<<endl; | |
| update(1,1,n,idx+1); | |
| } | |
| else if(x== 2) | |
| { | |
| cin >> v; | |
| update1(1,1,n,idx,v+1); | |
| } | |
| else if(x == 3) | |
| { | |
| cin >> a >>b; | |
| cout<<query(1,1,n,a+1,b+1)<<endl; | |
| } | |
| } | |
| return 0; | |
| } |
No comments:
Post a Comment