Algorithm
Problem Name: Data Structures -
https://www.hackerrank.com/challenges/bst-maintenance/problem?isFullScreen=true
In this HackerRank in Data Structures -
Consider a binary search tree T which is initially empty. Also, consider the first N positive integers {1, 2, 3, 4, 5, ....., N} and its permutation P {a1, a2, ..., aN}.
If we start adding these numbers to the binary search tree T, starting from a1, continuing with a2, ... (and so on) ..., ending with aN. After every addition we ask you to output the sum of distances between every pair of T's nodes.
Input Format
The first line of the input consists of the single integer N, the size of the list.
The second line of the input contains N single space separated numbers the permutation a1, a2, ..., aN itself.
Constraints
1 ≤ N ≤ 250000
Output Format
Output N lines.
On the ith line output the sum of distances between every pair of nodes after adding the first i numbers from the permutation to the binary search tree T
Sample Input #00
8
4 7 3 1 8 2 6 5
Sample Output #00
0
1
4
10
20
35
52
76
Explanation #00
After adding the first element, the distance is 0 as there is only 1 element
4
After adding the second element, the distance between 2 nodes is 1.
4
\
7
After adding the third element, the distance between every pair of elements is 2+1+1=4
4
/ \
3 7
After adding the fourth element, the distance between every pair of elements is 3 + 2 + 1 + 2 + 1 + 1 = 10
4
/ \
3 7
/
1
After adding the fifth element, the distance between every pair of elements is 4 + 3 + 2 + 1 + 3 + 2 + 1 + 2 + 1 + 1 = 20
4
/ \
3 7
/ \
1 8
After adding the sixth element, the distance between every pair of elements is 5 + 4 + 3 + 2 + 1 + 4 + 3 + 2 + 1 + 3 + 2 + 1 + 2 + 1 + 1 = 35
4
/ \
3 7
/ \
1 8
\
2
After adding the seventh element, the distance between every pair of elements is 5+5+4+3+2+1+4+4+3+2+1+3+3+2+1+2+2+1+1+1+2=52
4
/ \
3 7
/ / \
1 6 8
\
2
After adding the final element, the distance between every pair of elements is 6+5+5+4+3+2+1+5+4+4+3+2+1+4+3+3+2+1+3+2+2+1+2+1+1+2+1+3=76
4
/ \
3 7
/ / \
1 6 8
\ /
2 5
Code Examples
#1 Code Example with C Programming
Code -
C Programming
#include <stdio.h>
#include <stdlib.h>
typedef struct _node{
int x;
struct _node *next;
} lnode;
void init( int n ,int *tree);
void range_increment( int i, int j, int val ,int *tree);
int query( int i ,int *tree);
void insert_edge(int x,int y);
void dfs0(int u);
void preprocess();
int lca(int a,int b);
int dist(int u,int v);
void dfs1(int u,int p);
int dfs2(int u,int p);
void decompose(int root,int p);
int a[250000],cut[250000]={0},parent[250000],DP[18][250000],mid[750000],left[750000],right[750000],level[250000],sub[250000],N,NN,nn;
long long count[250000]={0},sum[250000]={0},con[250000]={0};
lnode *table[250000]={0};
int main(){
int x,y,z,leftd,rightd,i;
long long ans,aa=0;
scanf("%d",&NN);
for(i = 0; i < NN; i++)
scanf("%d",a+i);
init(NN,mid);
init(NN,left);
init(NN,right);
for(i = 0; i < NN; i++){
leftd=x=query(a[i]-1,left);
if(!x)
leftd=1;
rightd=y=query(a[i]-1,right);
if(!y)
rightd=NN;
z=query(a[i]-1,mid);
if(z)
insert_edge(z-1,a[i]-1);
range_increment(leftd-1,rightd-1,a[i]-z,mid);
range_increment(a[i]-1,rightd-1,a[i]-x,left);
range_increment(leftd-1,a[i]-1,a[i]-y,right);
}
preprocess();
decompose(a[NN/2]-1,-1);
for(i=0;i<NN;i++){
for(ans=sum[a[i]-1],x=a[i]-1;1;x=parent[x]){
if(parent[x]==-1)
break;
ans+=sum[parent[x]]-con[x]+dist(a[i]-1,parent[x])*(count[parent[x]]-count[x]);
}
for(x=a[i]-1;x!=-1;x=parent[x]){
sum[x]+=dist(a[i]-1,x);
count[x]++;
if(parent[x]!=-1)
con[x]+=dist(a[i]-1,parent[x]);
}
printf("%lld\n",aa+=ans);
}
return 0;
}
void init( int n ,int *tree){
N = 1;
while( N < n ) N *= 2;
int i;
for( i = 1; i < N + n; i++ ) tree[i] = 0;
}
void range_increment( int i, int j, int val ,int *tree){
for( i += N, j += N; i < = j; i = ( i + 1 ) / 2, j = ( j - 1 ) / 2 )
{
if( i % 2 == 1 ) tree[i] += val;
if( j % 2 == 0 ) tree[j] += val;
}
}
int query( int i ,int *tree){
int ans = 0,j;
for( j = i + N; j; j /= 2 ) ans += tree[j];
return ans;
}
void insert_edge(int x,int y){
lnode *t=malloc(sizeof(lnode)>;
t->x=y;
t->next=table[x];
table[x]=t;
t=malloc(sizeof(lnode));
t->x=x;
t->next=table[y];
table[y]=t;
return;
}
void dfs0(int u){
lnode *x;
for(x=table[u];x;x=x->next)
if(x->x!=DP[0][u]){
DP[0][x->x]=u;
level[x->x]=level[u]+1;
dfs0(x->x);
}
return;
}
void preprocess(){
int i,j;
level[a[0]-1]=0;
DP[0][a[0]-1]=a[0]-1;
dfs0(a[0]-1);
for(i = 1; i < 18; i++)
for(j = 0; j < NN; j++)
DP[i][j] = DP[i-1][DP[i-1][j]];
return;
}
int lca(int a,int b>{
int i;
if(level[a]>level[b]){
i=a;
a=b;
b=i;
}
int d = level[b]-level[a];
for(i = 0; i < 18; i++)
if(d&(1<<i))
b=DP[i][b];
if(a==b>return a;
for(i = 17; i >=0; i--)
if(DP[i][a]!=DP[i][b])
a=DP[i][a],b=DP[i][b];
return DP[0][a];
}
int dist(int u,int v){
return level[u] + level[v] - 2*level[lca(u,v)];
}
void dfs1(int u,int p){
sub[u]=1;
nn++;
lnode *x;
for(x=table[u];x;x=x->next)
if(x->x!=p && !cut[x->x]){
dfs1(x->x,u);
sub[u]+=sub[x->x];
}
return;
}
int dfs2(int u,int p){
lnode *x;
for(x=table[u];x;x=x->next)
if(x->x!=p && sub[x->x]>nn/2 && !cut[x->x])
return dfs2(x->x,u);
return u;
}
void decompose(int root,int p){
nn=0;
dfs1(root,root);
int centroid = dfs2(root,root);
parent[centroid]=p;
cut[centroid]=1;
lnode *x;
for(x=table[centroid];x;x=x->next)
if(!cut[x->x])
decompose(x->x,centroid);
return;
}
#2 Code Example with C++ Programming
Code -
C++ Programming
#include<cstdio>
#include<iostream>
#include<vector>
using namespace std;
struct Node
{
int val, numNode, depth;
long long heightSum;
Node* left;
Node* right;
Node* parent;
};
Node* root;
long long sumdist;
void Insert(int val)
{
if (root == NULL)
{
root = new Node;
root->val = val;
root->heightSum = 0;
root->numNode = 1;
root->depth = 0;
root->left = root->right = NULL;
root->parent = NULL;
}
else
{
Node* cur = root;
Node* tmp;
vector < Node*> v;
v.clear();
while (true)
{
if (cur->val < val)
{
if (cur->right == NULL)
{
tmp = cur;
cur->right = new Node;
if (cur->left != NULL)
v.push_back(cur->left);
cur = cur->right;
break;
}
else
{
if (cur->left != NULL)
v.push_back(cur->left);
cur = cur->right;
}
}
else
{
if (cur->left == NULL)
{
tmp = cur;
cur->left = new Node;
if (cur->right != NULL)
v.push_back(cur->right);
cur = cur->left;
break;
}
else
{
if (cur->right != NULL)
v.push_back(cur->right);
cur = cur->left;
}
}
}
cur->val = val;
cur->heightSum = 0;
cur->numNode = 1;
cur->left = cur->right = NULL;
cur->parent = tmp;
cur->depth = tmp->depth + 1;
long long leafdepth = cur->depth;
sumdist += (leafdepth)* (leafdepth + 1) / 2;
int height = 1;
cur = cur->parent;
while (cur != NULL)
{
cur->heightSum += height;
cur->numNode++;
cur = cur->parent;
height++;
}
int num = (int)v.size();
for (int i = 0; i < num; i++)
sumdist += v[i]->heightSum + (long long)v[i]->numNode * (leafdepth - v[i]->depth + 2);
}
}
void Traverse(Node* cur)
{
if (cur != NULL)
{
printf("val: %d, heightSum: %lld, numNode: %d, depth:%d\n", cur->val, cur->heightSum, cur->numNode, cur->depth);
Traverse(cur->left);
Traverse(cur->right);
}
}
int a[250000];
bool IsSpecial(int a[], int n)
{
int cnt = 0;
for (int i = 0; i < n; i++)
if (a[i] == i + 1)
cnt++;
if (cnt == n) return true;
cnt = 0;
for (int i = 0; i < n; i++)
if (a[i] == n - i)
cnt++;
if (cnt == n) return true;
return false;
}
int main()
{
int n;
scanf("%d", &n);
for (int i = 0; i < n; i++)
scanf("%d", &a[i]);
if (IsSpecial(a, n))
{
for (int i = 0; i < n; i++)
printf("%lld\n", (long long)i * (i + 1) * (i + 2) / 6);
}
else
{
sumdist = 0;
for (int i = 0; i < n; i++)
{
Insert(a[i]);
printf("%lld\n", sumdist);
}
}
return 0;
}
#3 Code Example with Java Programming
Code -
Java Programming
import java.util.Scanner;
public class Solution {
/**
* Sum of distance between every two node in tree.
*/
private static long cummulativeInterNodeDistance;
/**
* The root node.
*/
private static Node root;
/**
* Total nodes seen by element to be inserted.
*/
private static int nodesCount;
/**
* Insert value in BST.
* @param value
* @return cumulativeInterNodeDistance
*/
public static long insert(int value) {
nodesCount = 0;
Node node = new Node(value);
if (root == null) {
root = node;
} else {
root.insert(node);
}
return cummulativeInterNodeDistance;
}
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int numberOfInputs = in.nextInt();
for (int i = 0; i < numberOfInputs; i++) {
int value = in.nextInt();
long output = insert(value);
System.out.println(output);
}
}
/**
* Binary search tree node.
*
* @author kuldeep
*
*/
private static class Node {
/**
* Face value of node.
*/
private int value;
/**
* Number of children to this node on left.
*/
private int countOfLeftChildren;
/**
* Number of children to this node on right.
*/
private int countOfRightChildren;
/**
* Sum of distance of every left children to this node.
*/
private long cummulativeDistanceOfLeftChildren;
/**
* Sum of distance of every right children to this node.
*/
private long cummulativeDistanceOfRightChildren;
/**
* Node in left.
*/
private Node left;
/**
* Node in right.
*/
private Node right;
public Node(int value) {
super();
this.value = value;
this.countOfLeftChildren = 0;
this.countOfRightChildren = 0;
this.cummulativeDistanceOfLeftChildren = 0;
this.cummulativeDistanceOfRightChildren = 0;
}
/**
* Insert a node in the node.
* @param node node to be inserted.
* @return depth of inserted node from this node.
*/
private int insert (Node node) {
if (node.getValue() < value) {
nodesCount += countOfRightChildren + 1;
cummulativeInterNodeDistance += (cummulativeDistanceOfRightChildren + nodesCount);
if (left == null) {
left = node;
cummulativeDistanceOfLeftChildren = 1;
countOfLeftChildren = 1;
return 1;
} else {
int depthOfNewNode = left.insert(node) + 1;
countOfLeftChildren++;
cummulativeDistanceOfLeftChildren += depthOfNewNode;
return depthOfNewNode;
}
} else if (node.getValue() > value) {
nodesCount += countOfLeftChildren + 1;
cummulativeInterNodeDistance += (cummulativeDistanceOfLeftChildren + nodesCount);
if (right == null) {
right = node;
cummulativeDistanceOfRightChildren = 1;
countOfRightChildren = 1;
return 1;
} else {
int depthOfNewNode = right.insert(node) + 1;
countOfRightChildren++;
cummulativeDistanceOfRightChildren += depthOfNewNode;
return depthOfNewNode;
}
} else {
throw new RuntimeException("node already exists.");
}
}
/**
* @return the value
*/
public int getValue() {
return value;
}
}
}#4 Code Example with Javascript Programming
Code -
Javascript Programming
'use strict';
function update(n) {
var w = 0;
var c = 1;
while (n != null) {
if (n.dir == 1) {
w += n.w2 + n.c2 * c;
n.w1 += c;
n.c1++;
} else if (n.dir == 2) {
w += n.w1 + n.c1 * c;
n.w2 += c;
n.c2++;
}
c++;
n.dir = 0;
n = n.p;
}
return w;
}
function processData(input) {
var parse_fun = function (s) { return parseInt(s, 10); };
var lines = input.split('\n');
var N = parse_fun(lines.shift());
var A = lines.shift().split(' ').splice(0, N).map(parse_fun);
var res = new Array(N);
for (var i = 0; i < N; i++) {
res[i] = 0;
}
var w = 0;
var root = { p: null, v: A[0], n1: null, w1: 0, c1: 1, n2: null, w2: 0, c2: 1, dir: 0 };
res[0] = 0;
for (var i = 1; i < N; i++) {
var v = A[i];
var n = root;
var last = null;
while (n != null) {
if (v == n.v) {
last = null;
n = null;
break;
}
last = n;
if (v < n.v) {
n.dir = 1;
if (n.n1 == null) {
n.n1 = { p: n, v: v, n1: null, w1: 0, c1: 1, n2: null, w2: 0, c2: 1, dir: 0 };
n = null;
} else {
n = n.n1;
}
} else { // v > n.v
n.dir = 2;
if (n.n2 == null) {
n.n2 = { p: n, v: v, n1: null, w1: 0, c1: 1, n2: null, w2: 0, c2: 1, dir: 0 };
n = null;
} else {
n = n.n2;
}
}
}
w += update(last);
res[i] = w;
}
var out = '';
for (var i = 0; i < N; i++) {
out += res[i].toString(10) + '\n';
}
process.stdout.write(out);
}
process.stdin.resume();
process.stdin.setEncoding("ascii");
var _input = "";
process.stdin.on("data", function (input) { _input += input; });
process.stdin.on("end", function () { processData(_input); });