Clear Idea of Lazy Propagation (Segment Tree)

Segment Tree শেখার জন্য শাফায়েত ভাইয়ের এই টিউটোরিয়াল বেশ সহজ।

If you know already Segment Tree and Lazy Propagation it will be helpful for you. In the following picture the updating system is described.

  

Implementation of Segment Tree

/* Creating a segment tree. Then with the query() we can easily find the sum of any segment of the tree. */ #include<bits/stdc++.h> using namespace std; #define mx 100001 #define fi(a, b) for(int i=a; i<=b; i++) #define fd(a, b) for(int i=a; i>=b; i--) int n, m, ar[mx], tree[mx*3], ii, jj; void segmentt(int node, int st, int en){ if(st==en){ tree[node]=ar[st]; return ; } int left=node*2; int right=node*2+1; int mid=(st+en)/2; segmentt(left, st, mid); segmentt(right, mid+1, en); tree[node]=tree[left]+tree[right]; } int query(int node, int st, int en){ if(ii<=st && jj>=en) return tree[node]; // relevant segment else if(ii>en || jj<st) return 0; // out of the segment else{ // needs to divide again int left=2*node, right=node*2+1, mid=(st+en)/2; return (query(left, st, mid) + query(right, mid+1, en)); } } int main(){ cin>>n; fi(1, n) cin>>ar[i]; segmentt(1, 1, n); cin>>m; fi(1, m){ cin>>ii>>jj; cout<<query(1, 1, n)<<endl; } return 0; }

Print Longest Common Substring

/* You are given two string. Find the Largest Common Substring (not Subsequence). First, insert all the suffix (suffix of "suffix" are "x", "ix"......"suffix") of the first string in the "Trie", then check with the all the second-string-suffix's. */ #include<bits/stdc++.h> using namespace std; int cnt=1, ans=0, st=0; string s, ss; struct node{ int next[26+1]; }ar[10000]; void new_trie(int cur){ for(int i=0; i<=26; i++) ar[cur].next[i]=-1; } void insert(){ // Inserting the first string int sz=s.size(), cur=0, x; for(int i=0; i<sz; i++){ x=s[i]-'a'; if(ar[cur].next[x]==-1){ ar[cur].next[x]=cnt; new_trie(cnt++); } cur=ar[cur].next[x]; } } void find(int stt){ // Checking with the second string int sz=s.size(), cur=0, x, c=0; for(int i=0; i<sz; i++){ x=s[i]-'a'; if(ar[cur].next[x]==-1) break; cur=ar[cur].next[x]; c++; } if(c>ans){ // when larger counter(c) is found st=stt; ans=c; } } int main(){ int sz; new_trie(0); cin>>ss; // First String sz=ss.size(); for(int i=1; i<=sz; i++){ s=""; for(int ii=sz-i; ii<sz; ii++) s+=ss[ii]; insert(); } cin>>ss; // Second String sz=ss.size(); for(int i=1; i<=sz; i++){ s=""; for(int ii=sz-i; ii<sz; ii++) s=s+ss[ii]; find(sz-i); } for(int i=st, cc=1; cc<=ans; i++, cc++) cout<<ss[i]; return 0; }