Skip to content

Commit 295247c

Browse files
Pankajcoder1Pankajcoder1
committed
Segment tree
1 parent b76d2cd commit 295247c

File tree

2 files changed

+329
-0
lines changed

2 files changed

+329
-0
lines changed

‎Advance_Data_Structure/Fenwick_Tree.cpp

Lines changed: 159 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,159 @@
1+
/*
2+
written by Pankaj Kumar.
3+
country:-INDIA
4+
*/
5+
#include <bits/stdc++.h>
6+
#include <ext/pb_ds/assoc_container.hpp>
7+
#include <ext/pb_ds/tree_policy.hpp>
8+
using namespace std;
9+
using namespace __gnu_pbds;
10+
typedef long long ll ;
11+
typedef vector<ll> vl;
12+
#define speed cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
13+
/* Abbrevations */
14+
#define ff first
15+
#define ss second
16+
#define mp make_pair
17+
#define line cout<<endl;
18+
#define pb push_back
19+
#define Endl "\n"
20+
// loops
21+
#define forin(arr,n) for(ll i=0;i<n;i++) cin>>arr[i];
22+
// Some print
23+
#define no cout<<"NO"<<endl;
24+
#define yes cout<<"YES"<<endl;
25+
// sort
26+
#define all(V) (V).begin(),(V).end()
27+
#define srt(V) sort(all(V))
28+
#define srtGreat(V) sort(all(V),greater<ll>())
29+
// some extra
30+
#define printv(v) for(ll i=0;i<ll(v.size());i++){cout<<v[i]<<" ";} line;
31+
#define sz(V) ll(V.size())
32+
// template
33+
template <typename T>
34+
T mymax(T x,T y)
35+
{
36+
return (x>y)?x:y;
37+
}
38+
// function
39+
ll power(ll x,ll y,ll mod)
40+
{
41+
ll res=1;
42+
// x=x%mod;
43+
while(y>0)
44+
{
45+
if(y%2==1)
46+
{
47+
res*=x;
48+
// res=res%mod;
49+
}
50+
y/=2; x*=x; // x=x%mod;
51+
}
52+
return res;
53+
}
54+
ll str_to_num(string s)
55+
{
56+
return stoi(s);
57+
}
58+
59+
string num_to_str(ll num)
60+
{
61+
return to_string(num);
62+
}
63+
// datatype definination
64+
#define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
65+
class Point
66+
{
67+
public:
68+
ll x;
69+
ll y;
70+
ll z;
71+
ll getsum()
72+
{
73+
return x+y+z;
74+
}
75+
};
76+
/* ascii value
77+
A=65,Z=90,a=97,z=122
78+
*/
79+
/* -----------------------------------------------------------------------------------*/
80+
// to run ctrl+b
81+
ll getsum(vector<ll> v,vector<ll>& FenwickTree,ll index)
82+
{
83+
ll sum=0;
84+
while(index>0)
85+
{
86+
cout<<"index is "<<index<<endl;
87+
sum+=FenwickTree[index];
88+
index-=(index&(-index));
89+
}
90+
return sum;
91+
}
92+
93+
void update(vector<ll>& FenwickTree,ll index,ll n,ll value)
94+
{
95+
while(index<=n)
96+
{
97+
FenwickTree[index]+=value;
98+
index+=(index&(-index));
99+
}
100+
}
101+
ll solve()
102+
{
103+
cout<<"\tuse zero based indexing for query"<<endl;
104+
cout<<"size of array "<<endl;
105+
ll n,q,l,a,b;
106+
cin>>n;
107+
vector<ll> v(n,0);
108+
vector<ll> FenwickTree(n+1,0);
109+
cout<<"Enter element of array "<<endl;
110+
for(ll i=0;i<n;i++)
111+
{
112+
cin>>v[i];
113+
update(FenwickTree,i+1,n,v[i]);
114+
}
115+
cout<<"No of query "<<endl;
116+
cin>>q;
117+
while(q--)
118+
{
119+
cout<<"1.For update and 2. for sum"<<endl;
120+
cin>>l;
121+
if(l==1)
122+
{
123+
cout<<"Enter position and value "<<endl;
124+
ll pos=0,value;
125+
cin>>pos>>value;
126+
pos++;
127+
update(FenwickTree,pos,n,value);
128+
}
129+
else
130+
{
131+
cout<<"Sum upto:"<<endl;
132+
cin>>a;
133+
a++;
134+
ll sum=getsum(v,FenwickTree,a);
135+
cout<<"Required sum is "<<sum<<endl;
136+
}
137+
}
138+
return 0;
139+
}
140+
141+
int main()
142+
{
143+
speed;
144+
/* #ifndef ONLINE_JUDGE
145+
freopen("input.txt","r",stdin);
146+
freopen("output.txt","w",stdout);
147+
#endif */
148+
ll TestCase=1;
149+
// cin>>TestCase;
150+
while(TestCase--)
151+
{
152+
solve();
153+
}
154+
}
155+
/* stuff you should look before submission
156+
* int overflow
157+
* special test case (n=0||n=1||n=2)
158+
* don't get stuck on one approach if you get wrong answer
159+
*/

‎Advance_Data_Structure/Segment_Tree.cpp

Lines changed: 170 additions & 0 deletions
Original file line numberDiff line numberDiff line change
@@ -0,0 +1,170 @@
1+
/*
2+
written by Pankaj Kumar.
3+
country:-INDIA
4+
Institute: National Institute of Technology, Uttarakhand
5+
*/
6+
#include <bits/stdc++.h>
7+
// #include <ext/pb_ds/assoc_container.hpp>
8+
// #include <ext/pb_ds/tree_policy.hpp>
9+
using namespace std;
10+
// using namespace __gnu_pbds;
11+
typedef long long ll ;
12+
typedef vector<ll> vl;
13+
#define speed cin.tie(0);cout.tie(0);ios_base::sync_with_stdio(0);
14+
/* Abbrevations */
15+
#define ff first
16+
#define ss second
17+
#define mp make_pair
18+
#define line cout<<endl;
19+
#define pb push_back
20+
#define Endl "\n"
21+
// loops
22+
#define forin(arr,n) for(ll i=0;i<n;i++) cin>>arr[i];
23+
// Some print
24+
#define no cout<<"NO"<<endl;
25+
#define yes cout<<"YES"<<endl;
26+
// sort
27+
#define all(V) (V).begin(),(V).end()
28+
#define srt(V) sort(all(V))
29+
#define srtGreat(V) sort(all(V),greater<ll>())
30+
// some extra
31+
#define printv(v) for(ll i=0;i<ll(v.size());i++){cout<<v[i]<<" ";} line;
32+
#define precision(x) cout<<fixed<<setprecision(x);
33+
#define sz(V) ll(V.size())
34+
// template
35+
template <typename T>
36+
T mymax(T x,T y)
37+
{
38+
return (x>y)?x:y;
39+
}
40+
// function
41+
ll power(ll x,ll y,ll mod)
42+
{
43+
ll res=1;
44+
// x=x%mod;
45+
while(y>0)
46+
{
47+
if(y%2==1)
48+
{
49+
res*=x;
50+
// res=res%mod;
51+
}
52+
y/=2; x*=x; // x=x%mod;
53+
}
54+
return res;
55+
}
56+
ll str_to_num(string s)
57+
{
58+
return stoi(s);
59+
}
60+
61+
string num_to_str(ll num)
62+
{
63+
return to_string(num);
64+
}
65+
// datatype definination
66+
// #define ordered_set tree<ll,null_type,less<ll>,rb_tree_tag,tree_order_statistics_node_update>
67+
class Point
68+
{
69+
public:
70+
ll x;
71+
ll y;
72+
ll z;
73+
ll getsum()
74+
{
75+
return x+y+z;
76+
}
77+
};
78+
/* ascii value
79+
A=65,Z=90,a=97,z=122
80+
*/
81+
/* --------------------MAIN PROGRAM----------------------------*/
82+
// to run ctrl+b
83+
const ll N=3e5+5;
84+
vector<ll> tree(N,LONG_MAX);
85+
vector<ll> v(N,0);
86+
ll n,q;
87+
88+
void build(ll left,ll right,ll node){
89+
if(left==right){
90+
tree[node]=v[right];
91+
}
92+
else{
93+
ll mid=(right+left)/2;
94+
build(left,mid,2*node);
95+
build((mid+1),right,(2*node+1));
96+
tree[node]=min(tree[node*2],tree[2*node+1]);
97+
}
98+
}
99+
100+
void update(ll left,ll right,ll node,ll pos,ll value){
101+
if(left==right){
102+
v[pos]=value;
103+
tree[node]=value;
104+
}
105+
else{
106+
ll mid=(left+right)/2;
107+
if(left<=pos&&pos<=mid)
108+
update(left,mid,2*node,pos,value);
109+
else
110+
update(mid+1,right,2*node+1,pos,value);
111+
tree[node]=min(tree[2*node],tree[2*node+1]);
112+
}
113+
}
114+
115+
ll query(ll left,ll right,ll node,ll l,ll r){
116+
if(l>right||r<left)
117+
return LONG_MAX;
118+
if(l<=left&&right<=r)
119+
return tree[node];
120+
ll mid=(left+right)/2;
121+
ll p1=query(left,mid,2*node,l,r);
122+
ll p2=query(mid+1,right,2*node+1,l,r);
123+
return min(p1,p2);
124+
}
125+
126+
ll solve()
127+
{
128+
// cout<<"Enter size of array and no of query : ";
129+
cin>>n>>q;
130+
// cout<<"Now enetr array : ";
131+
for(ll i=1;i<=n;i++)
132+
cin>>v[i];
133+
build(1,n,1);
134+
while(q--){
135+
char ch;
136+
ll x,y;
137+
cin>>ch>>x>>y;
138+
if(ch=='q'){
139+
ll ans=query(1,n,1,x,y);
140+
cout<<ans<<endl;
141+
}
142+
else{
143+
update(1,n,1,x,y);
144+
}
145+
}
146+
return 0;
147+
}
148+
149+
int main()
150+
{
151+
speed;
152+
/* #ifndef ONLINE_JUDGE
153+
freopen("input.txt","r",stdin);
154+
freopen("output.txt","w",stdout);
155+
#endif */
156+
ll TestCase=1;
157+
// cin>>TestCase;
158+
while(TestCase--)
159+
{
160+
solve();
161+
}
162+
}
163+
/* -----------------END OF PROGRAM --------------------*/
164+
/*
165+
* stuff you should look before submission
166+
* constraint and time limit
167+
* int overflow
168+
* special test case (n=0||n=1||n=2)
169+
* don't get stuck on one approach if you get wrong answer
170+
*/

0 commit comments

Comments
 (0)