Skip to content

Navigation Menu

Sign in
Appearance settings

Search code, repositories, users, issues, pull requests...

Provide feedback

We read every piece of feedback, and take your input very seriously.

Saved searches

Use saved searches to filter your results more quickly
Appearance settings

Commit 295247c

Browse filesBrowse files
Pankajcoder1Pankajcoder1
committed
Segment tree
1 parent b76d2cd commit 295247c
Copy full SHA for 295247c

File tree

2 files changed

+329
-0
lines changed
Filter options

2 files changed

+329
-0
lines changed

‎Advance_Data_Structure/Fenwick_Tree.cpp

Copy file name to clipboard
+159Lines 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

Copy file name to clipboard
+170Lines 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 (0)
Morty Proxy This is a proxified and sanitized view of the page, visit original site.