/*
Time limit: 5000ms
Memory limit: 256mb
---------------------Copy the following code, complete it and submit---------------------
I, <Your Full Name>, am submitting the assignment for
an individual project.
I declare that the assignment here submitted is original except for
source material explicitly acknowledged, the piece of work, or a part
of the piece of work has not been submitted for more than one purpose
(i.e. to satisfy the requirements in two different courses) without
declaration. I also acknowledge that I am aware of University policy
and regulations on honesty in academic work, and of the disciplinary
guidelines and procedures applicable to breaches of such policy and
regulations, as contained in the University website
http://www.cuhk.edu.hk/policy/academichonesty/.
It is also understood that assignments without a properly signed
declaration by the student concerned will not be graded by the
teacher(s).
*/
#include <stdio.h>
#include <stdlib.h>
typedef struct AVLNode {
int key; /* BST key */
long long val; /* value associated with this key */
int height; /* height of this subtree (leaf = 1) */
int size; /* number of nodes in this subtree */
long long sum; /* sum of val over all nodes in subtree */
struct AVLNode *left;
struct AVLNode *right;
} AVLNode;
/* Function prototypes */
AVLNode * new_node(int key, long long val);
int get_height(AVLNode *n);
int get_size(AVLNode *n);
long long get_sum(AVLNode *n);
AVLNode * left_rotate(AVLNode *x);
AVLNode * right_rotate(AVLNode *y);
int get_balance(AVLNode *n);
AVLNode * rebalance(AVLNode *n);
AVLNode * avl_insert(AVLNode *root, int key, long long val);
AVLNode * avl_delete(AVLNode *root, int key);
long long query_sum(AVLNode *root, int L, int R);
/**
* @brief Allocate a new AVL node.
*/
AVLNode *new_node(int key, long long val) {
AVLNode *n = (AVLNode *)malloc(sizeof(AVLNode));
n->key = key;
n->val = val;
n->height = 1;
n->size = 1;
n->sum = val;
n->left = NULL;
n->right = NULL;
return n;
}
/** @brief Return the height of node n (0 if n is NULL). */
int get_height(AVLNode *n) { return n ? n->height : 0; }
/** @brief Return the size of node n (0 if n is NULL). */
int get_size(AVLNode *n) { return n ? n->size : 0; }
/** @brief Return the subtree value sum of node n (0 if n is NULL). */
long long get_sum(AVLNode *n) { return n ? n->sum : 0; }
/**
* @brief Return the balance factor of n.
* balance = height(left subtree) - height(right subtree).
* Returns 0 if n is NULL.
*/
int get_balance(AVLNode *n) {
if (!n) return 0;
return get_height(n->left) - get_height(n->right);
}
/**
* @brief Left-Rotation around x.
*
* x y
* / \ / \
* A y -> x C
* / \ / \
* B C A B
*/
AVLNode *left_rotate(AVLNode *x) {
// WRITE YOUR CODE HERE
}
/**
* @brief Right-Rotation around y.
*
* y x
* / \ / \
* x C -> A y
* / \ / \
* A B B C
*/
AVLNode *right_rotate(AVLNode *y) {
// WRITE YOUR CODE HERE
}
/**
* @brief Restore AVL balance at node n and return the new root.
* @param n root of the subtree to rebalance (already updated via update())
*/
AVLNode *rebalance(AVLNode *n) {
// WRITE YOUR CODE HERE
}
/**
* @brief Insert (key, val) into the AVL tree.
* If key already exists, the tree is unchanged.
* @param root current subtree root (may be NULL)
* @param key key to insert
* @param val value associated with key
*/
AVLNode *avl_insert(AVLNode *root, int key, long long val) {
// WRITE YOUR CODE HERE
}
/**
* @brief Delete key from the AVL tree.
* If key does not exist, the tree is unchanged.
* @param root current subtree root (may be NULL)
* @param key key to delete
*/
AVLNode *avl_delete(AVLNode *root, int key) {
// WRITE YOUR CODE HERE
}
/**
* @brief Compute the sum of values for all keys in [L, R].
* @param root AVL tree root
* @param L lower bound of key range (inclusive)
* @param R upper bound of key range (inclusive)
* @return sum of values for keys in [L, R]
*/
long long query_sum(AVLNode *root, int L, int R) {
// WRITE YOUR CODE HERE
}
// DO NOT MODIFY THE CODE BELOW
int main(void) {
int n;
if (scanf("%d", &n) != 1) return 0;
AVLNode *root = NULL;
for (int i = 0; i < n; ++i) {
int op;
scanf("%d", &op);
if (op == 1) {
int key; long long val;
scanf("%d %lld", &key, &val);
root = avl_insert(root, key, val);
} else if (op == 2) {
int key;
scanf("%d", &key);
root = avl_delete(root, key);
} else {
int l, r;
scanf("%d %d", &l, &r);
printf("%lld\n", query_sum(root, l, r));
}
}
/* free remaining nodes */
while (root) root = avl_delete(root, root->key);
return 0;
}
---------------------------------------End of Code---------------------------------------
## Maintaining a Key-Value Map with AVL-Tree
A **key-value map** (also called a dictionary or associative array) is one of the most fundamental data structures in computer science. It stores a collection of `(key, value)` pairs where every key is unique, and supports three core operations:
- **Insert** a new `(key, value)` pair.
- **Delete** an existing key (together with its associated value).
- **Query** -- retrieve information about the stored values.
Maps are used everywhere: database indices, caches, symbol tables in compilers, and routing tables in networks all rely on fast map implementations.
A naive implementation using an **unsorted array** requires $O(n)$ per lookup and insert. A **sorted array** supports $O(\log n)$ lookup via binary search but $O(n)$ insert/delete due to shifting. A **Binary Search Tree (BST)** achieves $O(h)$ for all three operations, where $h$ is the tree height -- but a plain BST degenerates to $O(n)$ when keys arrive in sorted order.
The **AVL-Tree** solves this by keeping the BST balanced at all times, guaranteeing $O(\log n)$ per operation regardless of input order.
In this problem, the map supports an additional **range sum query**: given a key range $[L, R]$, report the total value of all entries whose key falls in that range.
### Task
Implement a key-value map using an **AVL-Tree** to support the following operations:
1. **Insert** a `(key, value)` pair. If `key` already exists, ignore the operation.
2. **Delete** a `key`. If `key` does not exist, ignore the operation.
3. **Range Sum Query**: compute the **sum of values** for all keys in `[L, R]` (inclusive).
**Hint**
Augment each AVL-Tree node with a `sum` field -- the total value of all keys in that subtree. Then define a helper function:
$$\text{prefix\_sum}(x) = \sum_{\text{key} \le x} \text{value}$$
The range query is then: $\text{query}(L, R) = \text{prefix\_sum}(R) - \text{prefix\_sum}(L - 1)$.
---
### Input
- The first line contains $n$ ($1 \leq n \leq 10^5$), the number of operations.
- The next $n$ lines each describe one operation:
- `1 key value` -- Insert `(key, value)` ($1 \leq \text{key} \leq 10^6$, $1 \leq \text{value} \leq 10^9$)
- `2 key` -- Delete `key` ($1 \leq \text{key} \leq 10^6$)
- `3 L R` -- Range sum query over keys in $[L, R]$ ($1 \leq L \leq R \leq 10^6$)
### Output
For each **Range Sum Query** (`3 L R`), output a single integer on its own line. The answer may exceed $2^{31} - 1$; use a 64-bit integer type.
### Example
**Input**
```
7
1 3 10
1 1 5
1 5 8
3 1 4
1 2 3
2 3
3 1 5
```
**Output**
```
15
16
```
**Explanation**
Insert $3 \rightarrow 10$, $1 \rightarrow 5$, $5 \rightarrow 8$. Map: $\{1:5, 3:10, 5:8\}$.
- Query $[1, 4]$: keys $1, 3$ $\rightarrow$ $5 + 10 = 15$
Insert $2 \rightarrow 3$. Delete key $3$. Map: $\{1:5, 2:3, 5:8\}$.
- Query $[1, 5]$: keys $1, 2, 5$ $\rightarrow$ $5 + 3 + 8 = 16$