We will be discussing major topics here and actually difficult ones. You must know basic OOPs.
C structures Vs C++ Classes
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.
General structure of classes
class className{
private:
variable declaration;
function declaration;
public:
variable declaration;
function declaration;
};
Visibility labels(Public, private, protected
- 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.
Some terms and their meaning
- 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:
For CP lovers, here is class based implementation of segment trees and Euler tours, representing inheritance as well
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;
}