Implementation of Dynamic Segment Trees with Poly Hash Tables
#include <bits/stdc++.h>
using namespace std;
class PolyHash {
public:
PolyHash(const vector<int>& a, int p)
: a(a), p(p)
{
}
int hash(int k) const
{
int result = 0;
for (int i = 0; i < a.size(); i++) {
result = (result + a[i] * k) % p;
}
return result;
}
private:
vector<int> a;
int p;
};
class DynamicSegmentTreeWithPolyHash {
public:
DynamicSegmentTreeWithPolyHash(const vector<int>& a)
: a(a)
{
segmentSize = sqrt(a.size());
segmentTree.resize(2 * a.size());
for (int i = 0; i < a.size(); i += segmentSize) {
unordered_map<int, int> polyHashTable;
for (int j = i;
j < min(i + segmentSize, (int)a.size());
j++) {
polyHashTable[a[j]] = j - i;
segmentTree[a.size() + i / segmentSize]
+= a[j];
}
polyHashTables.push_back(polyHashTable);
}
}
int query(int l, int r) const
{
int sum = 0;
for (int i = l; i <= r;) {
if (i % segmentSize == 0
&& i + segmentSize - 1 < r) {
sum += segmentTree[a.size()
+ i / segmentSize];
i += segmentSize;
}
else {
sum += a[i];
i++;
}
}
return sum;
}
void update(int i, int x)
{
int segmentIndex = i / segmentSize;
int segmentStart = segmentIndex * segmentSize;
int segmentEnd = min(segmentStart + segmentSize,
(int)a.size());
segmentTree[a.size() + +segmentIndex] += x - a[i];
polyHashTables[segmentIndex].erase(a[i]);
polyHashTables[segmentIndex][x] = i - segmentStart;
a[i] = x;
}
void insert(int i, int x)
{
a.insert(a.begin() + i, x);
rebuild();
}
void remove(int i)
{
a.erase(a.begin() + i);
rebuild();
}
private:
void rebuild()
{
int n = a.size();
segmentSize = sqrt(n);
segmentTree.clear();
segmentTree.resize(2 * n);
polyHashTables.clear();
for (int i = 0; i < n; i += segmentSize) {
unordered_map<int, int> polyHashTable;
for (int j = i; j < min(i + segmentSize, n);
j++) {
polyHashTable[a[j]] = j - i;
segmentTree[n + i / segmentSize] += a[j];
}
polyHashTables.push_back(polyHashTable);
}
}
private:
vector<int> a;
int segmentSize;
vector<int> segmentTree;
vector<unordered_map<int, int> > polyHashTables;
};
int main()
{
vector<int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
DynamicSegmentTreeWithPolyHash dst(a);
cout << "Query(0, 4) = " << dst.query(0, 4) << endl;
dst.update(3, 100);
cout << "Query(2, 5) = " << dst.query(2, 5) << endl;
return 0;
}
#include <bits/stdc++.h>
using namespace std;
class PolyHash {
public:
PolyHash(const vector<int>& a, int p)
: a(a), p(p)
{
}
int hash(int k) const
{
int result = 0;
for (int i = 0; i < a.size(); i++) {
result = (result + a[i] * k) % p;
}
return result;
}
private:
vector<int> a;
int p;
};
class DynamicSegmentTreeWithPolyHash {
public:
DynamicSegmentTreeWithPolyHash(const vector<int>& a)
: a(a)
{
segmentSize = sqrt(a.size());
segmentTree.resize(2 * a.size());
for (int i = 0; i < a.size(); i += segmentSize) {
unordered_map<int, int> polyHashTable;
for (int j = i;
j < min(i + segmentSize, (int)a.size());
j++) {
polyHashTable[a[j]] = j - i;
segmentTree[a.size() + i / segmentSize]
+= a[j];
}
polyHashTables.push_back(polyHashTable);
}
}
int query(int l, int r) const
{
int sum = 0;
for (int i = l; i <= r;) {
if (i % segmentSize == 0
&& i + segmentSize - 1 < r) {
sum += segmentTree[a.size()
+ i / segmentSize];
i += segmentSize;
}
else {
sum += a[i];
i++;
}
}
return sum;
}
void update(int i, int x)
{
int segmentIndex = i / segmentSize;
int segmentStart = segmentIndex * segmentSize;
int segmentEnd = min(segmentStart + segmentSize,
(int)a.size());
segmentTree[a.size() + +segmentIndex] += x - a[i];
polyHashTables[segmentIndex].erase(a[i]);
polyHashTables[segmentIndex][x] = i - segmentStart;
a[i] = x;
}
void insert(int i, int x)
{
a.insert(a.begin() + i, x);
rebuild();
}
void remove(int i)
{
a.erase(a.begin() + i);
rebuild();
}
private:
void rebuild()
{
int n = a.size();
segmentSize = sqrt(n);
segmentTree.clear();
segmentTree.resize(2 * n);
polyHashTables.clear();
for (int i = 0; i < n; i += segmentSize) {
unordered_map<int, int> polyHashTable;
for (int j = i; j < min(i + segmentSize, n);
j++) {
polyHashTable[a[j]] = j - i;
segmentTree[n + i / segmentSize] += a[j];
}
polyHashTables.push_back(polyHashTable);
}
}
private:
vector<int> a;
int segmentSize;
vector<int> segmentTree;
vector<unordered_map<int, int> > polyHashTables;
};
int main()
{
vector<int> a = { 1, 2, 3, 4, 5, 6, 7, 8, 9, 10 };
DynamicSegmentTreeWithPolyHash dst(a);
cout << "Query(0, 4) = " << dst.query(0, 4) << endl;
dst.update(3, 100);
cout << "Query(2, 5) = " << dst.query(2, 5) << endl;
return 0;
}
Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.