We will be discussing major topics here and actually difficult ones. You must know basic OOPs.
Introduction
We know structures can be used to create user-defined data types in C and C++. But then why we need classes? We can have functions, constructors, etc in structures as well but what differentiates it from classes are lack of abstraction and inheritance(And actually many other things as well). We can hide certain members from outside world(abstraction) in a class but we can't do anything like this in structures. Also, we cannot overload an operator here. For example
struct complex{
float x,y;
};
// Structure for a complex number of form x+iy(i stands for iota)
complex c1,c2;
c1.x=1;
c1.y=2;
c2.x=3;
c2.y=3;
// c1=1+2i, c2=3+3i
complex c3=c1+c2;//Illegal statement in C because we cannot add these two structures.
class className{
private:
variable declaration;
function declaration;
public:
variable declaration;
function declaration;
};
- private: Data members labelled private are only available withing the class.
- public: Data members are available for the outside world as well.
- protected: Data members are not available for the whole world but are available to the inherited classes.
By default, all members are private.
- Abstraction: Data hiding. All those visibility labels are used for abstraction only. We can achieve data hiding using the visibility labels(private)
- Encapsulation: Data binding. This is just binding various data members and functions into a class. We actually do that, so it's kind of default behaviour.
- Polymorphism:
- Inheritance:
- Overloading:
Question Link: https://cses.fi/problemset/task/1138
#include<bits/stdc++.h>
using namespace std;
#define int long long int
const int mxN = 200001;
int inf = 1e18;
class segTree
{
private:
vector<int>tree;
vector<int>a;
void buildTree(int i, int st, int end, vector<int> &arr)
{
if(st == end)
{
tree[i] = arr[st];
return;
}
int mid = st + (end - st) / 2;
int lchild = 2 * i + 1;
int rchild = 2 * i + 2;
buildTree(lchild, st, mid, arr);
buildTree(rchild, mid + 1, end, arr);
tree[i] = tree[lchild] + tree[rchild];
}
int queryPrivate(int i, int segStart, int segEnd, int l, int r)
{
if(segEnd < l || segStart > r)return 0;
if(segEnd <= r && segStart >= l)
return tree[i];
int lchild = 2 * i + 1;
int rchild = 2 * i + 2;
int mid = segStart + (segEnd - segStart) / 2;
int resL = queryPrivate(lchild, segStart, mid, l, r);
int resR = queryPrivate(rchild, mid + 1, segEnd, l, r);
return resL + resR;
}
void upd(int i, int st, int end, int ind, int newVal)
{
if(st == end)
{
tree[i] = newVal;
return;
}
int mid = st + (end - st) / 2;
if(ind <= mid)
upd(2 * i + 1, st, mid, ind, newVal);
else
upd(2 * i + 2, mid + 1, end, ind, newVal);
tree[i] = tree[2 * i + 1] + tree[2 * i + 2];
}
public:
void build(vector<int> &arr)
{
int n = arr.size();
tree.resize(4 * n + 1);
for(int i = 0; i < 4 * n + 1; i++)tree[i] = inf;
buildTree(0, 0, n — 1, arr);
a = arr;
}
int queryTree(int l, int r)
{
int n = a.size();
return queryPrivate(0, 0, n — 1, l, r);
}
void updateTree(int indToChange, int newVal)
{
int n = a.size();
upd(0, 0, n - 1, indToChange, newVal);
}
};
// Inherited segTree class to Tree class
class Tree : public segTree
{
vector<int>adj[mxN];
vector<int>val;
vector<int>in;
vector<int>out;
vector<int>eTour;
segTree s;
public:
Tree(vector<int>arr)
{
// cout<<"u";
int n = arr.size();
val.resize(n);
in.resize(n);
out.resize(n);
for(int i = 0; i < n; i++)in[i] = -1;
for(int i = 0; i < n; i++)out[i] = -1;
val = arr;
}
void dfs(int src, vector<bool> &vis)
{
vis[src] = 1;
eTour.push_back(src);
for(auto it : adj[src])
{
if(!vis[it])
dfs(it, vis);
}
eTour.push_back(src);
}
void eulerTour()
{
vector<bool>vis(val.size());
dfs(0, vis);
for(int i = 0; i < eTour.size(); i++)
{
if(in[eTour[i]] == -1)
in[eTour[i]] = i;
else
out[eTour[i]] = i;
}
for(int i = 0; i < eTour.size(); i++)
{
if(in[eTour[i]]==i)
eTour[i] = val[eTour[i]];
else
eTour[i] = -val[eTour[i]];
// cout<<eTour[i]<<" ";
}
// cout<<"\n";
build(eTour);
}
void addEdge(int x, int y)
{
adj[x — 1].push_back(y — 1);
adj[y — 1].push_back(x — 1);
}
int query(int node)
{
node--;
return queryTree(0, in[node]);
}
void update(int node, int x)
{
node--;
updateTree(in[node], x);
updateTree(out[node], -x);
val[node] = x;
}
};
int32_t main()
{
// This is the holy code of the demon AB-DUDE
// This is the code of the question : https://cses.fi/problemset/task/1137/
// We used Euler Tour and Segment Trees for this
// Just do a Euler tour of type 2 on the tree and make a basic segment tree on the array
// Now, we can just use in and out arrays for the positions of the nodes in the euler tour array
int n, q;
cin >> n >> q;
vector<int>a(n);
for(int i = 0; i < n; i++)cin >> a[i];
Tree tr(a);
for (int i = 0; i < n - 1; ++i)
{
int x, y;
cin >> x >> y;
tr.addEdge(x, y);
}
tr.eulerTour();
for(int i = 0; i < q; i++)
{
int t;
cin >> t;
if(t == 1)
{
int s, x;
cin >> s >> x;
tr.update(s, x);
}
else
{
int s;
cin >> s;
cout << tr.query(s) << "\n";
}
}
return 0;
}
Member variables are different for different objects but member functions are the same, which is quite obvious.
Static Data members As we saw in memory allocation diagram, copies of member variables are made for different objects. But if we want a common variable for all objects of class? For example in an employee class, we need to find the number of employees at a specific time. We can do it using a global variable but that variable can interfere in the whole working of program. We can use a static data member. Static members are initialized to 0 and one important thing to note is that static members defined outside the class and can be initialized