FAST Kit provides the Segment Map to query and maintain range information, implementing efficient range queries and updates for data sequences. As a data structure designed for efficient management of range information, the Segment Map is well suited for scenarios requiring frequent statistical analysis or modifications over specific data segments. Its typical operations include point updates, range updates, and range queries.
While there are multiple ways to implement Segment Maps, the most common method uses a binary tree, frequently referred to as a Segment Tree. Compared with directly traversing ranges, a Segment Map reduces the time complexity of many range operations from 
to 
. It provides significant advantages when processing large-scale data and serves as a data structure foundation for building high-performance, responsive apps.
API Description
For details about the APIs, please refer to the API Reference.
| API | Description |
|---|---|
| FAST_EXPORT FAST_ErrorCode HMS_FAST_SegmentMap_CreateConfig (FAST_SegmentMapConfig **config) | Creates the opaque configuration of a Segment Map. |
| FAST_EXPORT void HMS_FAST_SegmentMap_DestroyConfig (FAST_SegmentMapConfig *config) | Destroys the opaque configuration of a Segment Map. |
| FAST_EXPORT FAST_ErrorCode HMS_FAST_SegmentMap_SetQueryType (FAST_SegmentMapConfig *config, FAST_SegmentMapQueryType type) | Sets the query type in the opaque configuration of a Segment Map. |
| FAST_EXPORT FAST_ErrorCode HMS_FAST_SegmentMap_SetUpdateType (FAST_SegmentMapConfig *config, FAST_SegmentMapUpdateType type) | Sets the update type in the opaque configuration of a Segment Map. |
| FAST_EXPORT FAST_ErrorCode HMS_FAST_SegmentMap_Create (FAST_SegmentMapHandle *handle, size_t size, const int32_t *array, FAST_SegmentMapConfig *config) | Creates a Segment Map. |
| FAST_EXPORT void HMS_FAST_SegmentMap_Destroy (FAST_SegmentMapHandle handle) | Destroys a Segment Map instance and releases its memory. Calling this function again after destruction is considered undefined behavior. |
| FAST_EXPORT FAST_ErrorCode HMS_FAST_SegmentMap_Update (FAST_SegmentMapHandle handle, size_t left, size_t right, int32_t value) | Performs a range update (value assignment, addition, or subtraction) on a Segment Map based on the configuration. |
| FAST_EXPORT FAST_ErrorCode HMS_FAST_SegmentMap_Query (FAST_SegmentMapHandle handle, size_t left, size_t right, int32_t *result) | Performs a range query on a Segment Map to return statistics like the maximum, minimum, or sum based on the configuration. |
Development Procedure
-
Link the related dynamic library in the CMake script.
find_library( lib_fast_ads NAMES fast_ads ) target_link_libraries(entry PRIVATE ${lib_fast_ads}) -
Call HMS_FAST_SegmentMap_CreateConfig to generate a Segment Map configuration instance (FAST_SegmentMapConfig).
-
Call HMS_FAST_SegmentMap_SetQueryType to set the query type.
-
Call HMS_FAST_SegmentMap_SetUpdateType to set the update type.
-
Call HMS_FAST_SegmentMap_Create to generate a Segment Map instance (FAST_SegmentMapHandle). After the instance is generated, the query and update types cannot be changed.
-
Call HMS_FAST_SegmentMap_Query to perform efficient range queries.
-
Call HMS_FAST_SegmentMap_Update to perform efficient range updates.
-
Call HMS_FAST_SegmentMap_Destroy to destroy the Segment Map instance.
-
Call HMS_FAST_SegmentMap_DestroyConfig to destroy the Segment Map configuration instance.
#include <cassert>
#include <iostream>
#include "FASTKit/fast_ads_segment_map.h"
FAST_ErrorCode demoSegmentMapSumSet()
{
FAST_SegmentMapConfig *config = nullptr;
FAST_SegmentMapHandle handle = nullptr;
int32_t *array = nullptr;
FAST_ErrorCode ret;
ret = HMS_FAST_SegmentMap_CreateConfig(&config);
if (ret != FAST_ERROR_CODE_SUCCESS) {
return ret;
}
do {
// Initialize configuration.
ret = HMS_FAST_SegmentMap_SetQueryType(config, FAST_SEGMENTMAP_QUERY_TYPE_SUM);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
ret = HMS_FAST_SegmentMap_SetUpdateType(config, FAST_SEGMENTMAP_UPDATE_TYPE_SET);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
// Initialize the array.
size_t size = 10;
array = new int32_t[size];
for (size_t i = 0; i < size; ++i) {
array[i] = i + 1;
}
// array = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
// Create a Segment Map instance.
ret = HMS_FAST_SegmentMap_Create(&handle, size, array, config);
// The initial Segment Map is {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}.
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
int32_t result;
// First query: Query the sum of the range [0, 5).
ret = HMS_FAST_SegmentMap_Query(handle, 0, 5, &result);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
assert(result == 15); // 1 + 2 + 3 + 4 + 5 = 15
// First update: Set each element in the range [3, 7) to -1.
ret = HMS_FAST_SegmentMap_Update(handle, 3, 7, -1);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
// The Segment Map is updated to {1, 2, 3, -1, -1, -1, -1, 8, 9, 10}.
// Second query: Query the sum of the range [0, 5).
ret = HMS_FAST_SegmentMap_Query(handle, 0, 5, &result);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
assert(result == 4); // 1 + 2 + 3 - 1 - 1 = 4
// Second update: Set each element in the range [5, 9) to 2.
ret = HMS_FAST_SegmentMap_Update(handle, 5, 9, 2);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
// The Segment Map is updated to {1, 2, 3, -1, -1, 2, 2, 2, 2, 10}.
// Third query: Query the sum of the range [0, 10).
ret = HMS_FAST_SegmentMap_Query(handle, 0, 10, &result);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
assert(result == 22); // 1 + 2 + 3 -1 -1 + 2 + 2 + 2 + 2 + 10 = 22
// Third update: Set each element in the range [0, 3) to 0.
ret = HMS_FAST_SegmentMap_Update(handle, 0, 3, 0);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
// The Segment Map is updated to {0, 0, 0, -1, -1, 2, 2, 2, 2, 10}.
// Fourth query: Query the sum of the range [3, 7).
ret = HMS_FAST_SegmentMap_Query(handle, 3, 7, &result);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
assert(result == 2); // -1 -1 + 2 + 2 = 2
// Fourth update: Set each element in the range [7, 10) to 5.
ret = HMS_FAST_SegmentMap_Update(handle, 7, 10, 5);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
// The Segment Map is updated to {0, 0, 0, -1, -1, 2, 2, 5, 5, 5}.
// Fifth query: Query the sum of the range [0, 10).
ret = HMS_FAST_SegmentMap_Query(handle, 0, 10, &result);
if (ret != FAST_ERROR_CODE_SUCCESS) {
break;
}
assert(result == 17); // 0 + 0 + 0 -1 -1 + 2 + 2 + 5 + 5 + 5 = 17
} while (0);
// Destroy the Segment Map instance.
HMS_FAST_SegmentMap_Destroy(handle);
// Destroy the configuration.
HMS_FAST_SegmentMap_DestroyConfig(config);
// Release the array.
if (array) {
delete[] array;
}
return ret;
}