Created
December 18, 2011 09:50
-
-
Save kogemrka/1492888 to your computer and use it in GitHub Desktop.
Дерево отрезков
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
#include <vector> | |
#include <stdexcept> | |
#include <iomanip> | |
#include <sstream> | |
template <class T> | |
class SumPolicy | |
{ | |
public: | |
T neutral() const | |
{ | |
return T(); | |
} | |
T operator()(T a, T b) const | |
{ | |
return a + b; | |
} | |
}; | |
template <class T> | |
class MaxPolicy | |
{ | |
public: | |
MaxPolicy(T infinite): | |
inf(infinite) | |
{} | |
T neutral() const | |
{ | |
return inf; | |
} | |
T operator()(T a, T b) const | |
{ | |
return std::max(a, b); | |
} | |
private: | |
T inf; | |
}; | |
template <class T, template <typename = T> class Policy = SumPolicy > | |
class SegmentTree | |
{ | |
public: | |
template <class ForwardIterator> | |
SegmentTree(ForwardIterator first, ForwardIterator last, const Policy<T>&); | |
SegmentTree(const std::vector<T>& values, const Policy<T>&); | |
T get(size_t index) const; | |
T get(std::pair<size_t, size_t> slice) const; | |
void set(size_t index, const T& value); | |
void push_back(const T& elem); | |
void pop_back(); | |
private: | |
size_t size; | |
size_t realCount; | |
std::vector<T> tree; | |
Policy<T> policy; | |
static size_t degreeOf2(size_t n); | |
size_t indexInTree(size_t index) const; | |
void makeTree(const std::vector<T>& values); | |
void update(size_t node, size_t leftLimit, size_t rightLimit, size_t modified, T newValue); | |
T calcSegment(size_t node, size_t leftLimit, size_t rightLimit, size_t left, size_t right) const; | |
}; | |
int main() | |
{ | |
std::vector<int> v1; | |
for (int i = 0; i < 10; ++i) | |
v1.push_back(rand() % 10); | |
SegmentTree<int, SumPolicy> tree1(v1, SumPolicy<int>()); | |
std::string answer; | |
std::cout << "Задать запрос?" << std::endl; | |
std::getline(std::cin, answer, '\n'); | |
while (answer == "y") | |
{ | |
for (size_t i = 0; i < v1.size(); ++ i) | |
std::cout << std::setw(3) << i; | |
std::cout << std::endl; | |
for (size_t i = 0; i < v1.size(); ++ i) | |
std::cout << std::setw(3) << v1[i]; | |
std::cout << std::endl; | |
size_t a, b; | |
std::string query; | |
std::getline(std::cin, query, '\n'); | |
std::istringstream(query) >> a >> b; | |
std::cout << tree1.get(std::make_pair(a, b)) << std::endl; | |
std::cout << "Задать запрос?" << std::endl; | |
std::getline(std::cin, answer, '\n'); | |
size_t index = rand() % v1.size(); | |
v1[index] = rand() % 10; | |
tree1.set(index, v1[index]); | |
} | |
return 0; | |
} | |
template <class T, template <typename = T> class Policy> | |
template <class ForwardIterator> | |
SegmentTree<T, Policy>::SegmentTree(ForwardIterator first, ForwardIterator last, const Policy<T>& policyObj): | |
policy(policyObj) | |
{ | |
policy = policyObj; | |
std::vector<T> values; | |
std::copy(first, last, values.end()); | |
makeTree(values); | |
} | |
template <class T, template <typename = T> class Policy> | |
SegmentTree<T, Policy>::SegmentTree(const std::vector<T>& values, const Policy<T>& policyObj): | |
policy(policyObj) | |
{ | |
makeTree(values); | |
} | |
template <class T, template <typename = T> class Policy> | |
void SegmentTree<T, Policy>::makeTree(const std::vector<T>& values) | |
{ | |
size = values.size(); | |
realCount = degreeOf2(values.size()); | |
tree.resize(realCount * 2 - 1, policy.neutral()); | |
for (size_t i = 0; i < size; ++i) | |
tree[realCount - 1 + i] = values[i]; | |
size_t start = realCount / 2; | |
size_t end = realCount; | |
while (start != 0) | |
{ | |
for (size_t i = start; i < end; ++i) | |
tree[i - 1] = policy(tree[i*2 - 1], tree[i*2]); | |
start /= 2; | |
end /= 2; | |
} | |
} | |
template <class T, template <typename = T> class Policy > | |
size_t SegmentTree<T, Policy>::degreeOf2(size_t n) | |
{ | |
size_t result = 1; | |
while (result < n) | |
result <<= 1; | |
return result; | |
} | |
template <class T, template <typename = T> class Policy > | |
size_t SegmentTree<T, Policy>::indexInTree(size_t index) const | |
{ | |
return realCount + index - 1; | |
} | |
template <class T, template <typename = T> class Policy > | |
T SegmentTree<T, Policy>::get(size_t index) const | |
{ | |
if (index >= size) | |
throw std::range_error("Index out of range"); | |
return tree[indexInTree(index)]; | |
} | |
template <class T, template <typename = T> class Policy > | |
void SegmentTree<T, Policy>::set(size_t index,const T& value) | |
{ | |
if (index >= size) | |
throw std::range_error("Index out of range"); | |
update(0, 0, realCount - 1, index, value); | |
} | |
template <class T, template <typename = T> class Policy > | |
void SegmentTree<T, Policy>::update(size_t node, size_t leftLimit, size_t rightLimit, size_t modified, T newValue) | |
{ | |
if (leftLimit == rightLimit) | |
{ | |
tree[indexInTree(modified)] = newValue; | |
return; | |
} | |
size_t middle = (rightLimit + leftLimit) / 2; | |
if (modified < middle) | |
update((node+1)*2 - 1, leftLimit, middle, modified, newValue); | |
else | |
update((node+1)*2, middle + 1, rightLimit, modified, newValue); | |
tree[node] = policy(tree[(node+1)*2 - 1], tree[(node+1)*2]); | |
} | |
template <class T, template <typename = T> class Policy > | |
T SegmentTree<T, Policy>::get(std::pair<size_t, size_t> slice) const | |
{ | |
if (slice.first >= size || slice.second >= size || slice.first > slice.second) | |
throw std::range_error("Index out of range"); | |
return calcSegment(0, 0, realCount - 1, slice.first, slice.second); | |
} | |
template <class T, template <typename = T> class Policy > | |
T SegmentTree<T, Policy>::calcSegment(size_t node, size_t leftLimit, size_t rightLimit, size_t left, size_t right) const | |
{ | |
if (left > right) | |
return policy.neutral(); | |
if (left == leftLimit && right == rightLimit) | |
return tree[node]; | |
size_t middle = (leftLimit + rightLimit) / 2; | |
return policy(calcSegment ((node+1)*2 - 1, leftLimit, middle, left, std::min(right,middle)), | |
calcSegment ((node+1)*2, middle+1, rightLimit, std::max(left,middle + 1), right)); | |
} | |
template <class T, template <typename = T> class Policy > | |
void SegmentTree<T, Policy>::push_back(const T& elem) | |
{ | |
if (size != realCount) | |
{ | |
++size; | |
set(size - 1, elem); | |
} | |
else | |
{ | |
std::vector<T> values; | |
for (size_t i = 0; i < size; ++i) | |
values.push_back(tree[realCount / 2 - 1 + i]); | |
values.push_back(elem); | |
SegmentTree tmp(values, policy); | |
*this = tmp; | |
} | |
} | |
template <class T, template <typename = T> class Policy > | |
void SegmentTree<T, Policy>::pop_back() | |
{ | |
if (size - 1 != realCount / 4) | |
{ | |
set(size - 1, policy.neutral()); | |
--size; | |
} | |
else | |
{ | |
std::vector<T> values; | |
for (size_t i = 0; i < size - 1; ++i) | |
values.push_back(tree[realCount / 2 - 1 + i]); | |
SegmentTree tmp(values, policy); | |
*this = tmp; | |
} | |
} |
Sign up for free
to join this conversation on GitHub.
Already have an account?
Sign in to comment